আমাদের বন্ধনী সম্বলিত একটি স্ট্রিং দেওয়া হয়েছে এবং কাজটি হল বন্ধনী ক্রমগুলির জোড়ার গণনা করা যা এমনভাবে গঠিত হতে পারে যাতে বন্ধনীগুলি সুষম হয়৷
বন্ধনীগুলিকে ভারসাম্যপূর্ণ বলা হয় যখন খোলা এবং বন্ধ বন্ধনীগুলির সমান সংখ্যক থাকে। জোড়া গঠনের জন্য একবার ব্যবহৃত বন্ধনীকে দুইবার বিবেচনা করা যাবে না।
ইনপুট − স্ট্রিং পরান[] ={ ")()()), "(", ")(", ")(", ")" }
আউটপুট − বন্ধনীর ক্রমগুলির জোড়ার সংখ্যা যেমন বন্ধনী ভারসাম্যপূর্ণ হয়:1
ব্যাখ্যা − আমরা গণনাটি আরও ভালভাবে গণনা করতে স্ট্রিংয়ের প্রতিটি সেট নেব। প্রথম এলিমেন্টটিকে “)()()” হিসেবে ধরা যাক যেখানে 4টি ক্লোজিং বন্ধনী এবং 2টি খোলা বন্ধনী রয়েছে তাই আমরা একটি সুষম বন্ধনী ক্রম তৈরি করতে ঠিক 2টি বন্ধ বন্ধনী সমন্বিত স্ট্রিংটির পরবর্তী উপাদানটি খুঁজব যা নয় সেখানে স্ট্রিং তাই আমরা এটি বাতিল করে পরের জন্য যেতে হবে. সুতরাং সমান খোলা এবং বন্ধ বন্ধনী সহ বৈধ জোড়াটি (2, 5) তাই গণনা হল 1৷
ইনপুট − স্ট্রিং পরান[] ={ ")()()), "((", "(", ")(", ")(", ")"}
আউটপুট − বন্ধনীর ক্রমগুলির জোড়ার সংখ্যা যেমন বন্ধনী ভারসাম্যপূর্ণ হয়:1
ব্যাখ্যা − বৈধ সুষম বন্ধনী জোড়া হল (1, 2) এবং (3, 6)। তাই গণনা হল 2।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
স্ট্রিংটি ইনপুট করুন এবং length() ফাংশন ব্যবহার করে একটি স্ট্রিংয়ের দৈর্ঘ্য গণনা করুন এবং আরও প্রক্রিয়াকরণের জন্য ডেটা পাস করুন৷
-
বন্ধনীর বৈধ জোড়া সংরক্ষণ করতে একটি অস্থায়ী পরিবর্তনশীল গণনা নিন এবং একটি um_1 এবং um_2 ভেরিয়েবল তৈরি করুন unordered_map টাইপের৷
-
0 থেকে একটি স্ট্রিং আকার পর্যন্ত অন্য লুপ FOR শুরু করুন
-
লুপের ভিতরে, str কে paran[i] হিসাবে সেট করুন অর্থাৎ বন্ধনীর প্রথম উপাদান এবং আবার একটি স্ট্রিংয়ের দৈর্ঘ্য গণনা করুন।
-
প্রথম এবং শেষ হিসাবে একটি অস্থায়ী পরিবর্তনশীল নিন এবং 0
দিয়ে শুরু করুন -
একটি স্ট্রিং এর দৈর্ঘ্য পর্যন্ত j থেকে 0 পর্যন্ত আরেকটি লুপ FOR শুরু করুন
-
লুপের ভিতরে, IF str[j] =‘(' তারপর প্রথমটিকে 1 দ্বারা বৃদ্ধি করুন ELSE চেক করুন IF first =1 তারপর প্রথমটিকে 1 ELSE কমিয়ে শেষটি 1 দ্বারা বৃদ্ধি করুন৷
-
এখন IF প্রথমে 1 এবং শেষটি 0 তারপর um_1[প্রথম]++ সেট করুন এবং IF শেষটি 1 এবং প্রথমটি 0 তারপর um_2[lst]++ সেট করুন এবং IF প্রথমটি 0 এবং শেষটিও 0 তারপর গণনা বৃদ্ধি করুন 1 দ্বারা।
-
গণনা হিসাবে গণনা সেট করুন / 2
-
0 থেকে um_1 পর্যন্ত লুপ শুরু করুন এবং um_1.second এবং um_2.first
থেকে সর্বনিম্ন মান হিসাবে গণনা সেট করুন -
গণনা ফেরত দিন
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int parentheses(string paran[], int size){
int count = 0;
unordered_map<int, int> um_1, um_2;
for (int i = 0; i < size; i++){
string str = paran[i];
int len = str.length();
int first = 0;
int last = 0;
for (int j = 0; j < len; j++){
if (str[j] == '('){
first++;
}
else{
if (first==1){
first--;
}
else{
last++;
}
}
}
if(first==1 && last!=1){
um_1[first]++;
}
if (last==1 && first!=1){
um_2[last]++;
}
if(first!=1 && last!=1){
count++;
}
}
count = count / 2;
for (auto it : um_1){
count += min(it.second, um_2[it.first]);
}
return count;
}
int main(){
string paran[] = { ")()())", "(", ")(", ")(", ")"};
int size = sizeof(paran) / sizeof(paran[0]);
cout<<"Count of pairs of parentheses sequences such that parentheses are balanced are:
"<<parentheses(paran, size);
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of pairs of parentheses sequences such that parentheses are balanced are: 1
