ধরুন আমাদের একটি অভিব্যক্তি আছে। অভিব্যক্তির কিছু বন্ধনী আছে; আমাদের পরীক্ষা করতে হবে বন্ধনীগুলি সুষম কিনা। বন্ধনীর ক্রম হল (), {} এবং []। ধরুন দুটি স্ট্রিং আছে। "()[(){()}]" এটি বৈধ, কিন্তু "{[}]" অবৈধ৷
কাজটি সহজ; আমরা এটি করার জন্য স্ট্যাক ব্যবহার করব। সমাধান পেতে আমাদের এই পদক্ষেপগুলি অনুসরণ করা উচিত −
-
এটি নিঃশেষ না হওয়া পর্যন্ত অভিব্যক্তির মাধ্যমে অতিক্রম করুন
-
যদি বর্তমান অক্ষরটি খোলা বন্ধনী হয় যেমন (, { বা [, তারপর স্ট্যাকের মধ্যে পুশ করুন
-
যদি বর্তমান অক্ষরটি বন্ধ বন্ধনী হয় যেমন ), } বা ], তাহলে স্ট্যাক থেকে পপ করুন এবং পপ করা বন্ধনীটি বর্তমান অক্ষরের প্রারম্ভিক বন্ধনীর সাথে সামঞ্জস্যপূর্ণ কিনা তা পরীক্ষা করুন, তবে এটি ঠিক আছে, অন্যথায়, এটি ভারসাম্যপূর্ণ নয়৷
-
-
স্ট্রিং নিঃশেষ হয়ে যাওয়ার পরে, যদি স্ট্যাকের মধ্যে কিছু প্রারম্ভিক বন্ধনী অবশিষ্ট থাকে, তাহলে স্ট্রিংটি ভারসাম্যপূর্ণ নয়৷
উদাহরণ
#include <iostream>
#include <stack>
using namespace std;
bool isBalancedExp(string exp) {
stack<char> stk;
char x;
for (int i=0; i<exp.length(); i++) {
if (exp[i]=='('||exp[i]=='['||exp[i]=='{') {
stk.push(exp[i]);
continue;
}
if (stk.empty())
return false;
switch (exp[i]) {
case ')':
x = stk.top();
stk.pop();
if (x=='{' || x=='[')
return false;
break;
case '}':
x = stk.top();
stk.pop();
if (x=='(' || x=='[')
return false;
break;
case ']':
x = stk.top();
stk.pop();
if (x =='(' || x == '{')
return false;
break;
}
}
return (stk.empty());
}
int main() {
string expresion = "()[(){()}]";
if (isBalancedExp(expresion))
cout << "This is Balanced Expression";
else
cout << "This is Not Balanced Expression";
} ইনপুট
"()[(){()}]" আউটপুট
This is Balanced Expression
