ধরুন আমাদের একটি অভিব্যক্তি আছে। অভিব্যক্তির কিছু বন্ধনী আছে; আমাদের পরীক্ষা করতে হবে বন্ধনীগুলি সুষম কিনা। বন্ধনীর ক্রম হল (), {} এবং []। ধরুন দুটি স্ট্রিং আছে। "()[(){()}]" এটি বৈধ, কিন্তু "{[}]" অবৈধ৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- এটি নিঃশেষ না হওয়া পর্যন্ত অভিব্যক্তির মধ্য দিয়ে অতিক্রম করুন
- যদি বর্তমান অক্ষরটি খোলা বন্ধনী হয় যেমন (, { বা [, তারপর স্ট্যাকের মধ্যে পুশ করুন
- যদি বর্তমান অক্ষর বন্ধনী বন্ধ করে থাকে যেমন ), } বা ], তাহলে স্ট্যাক থেকে পপ করুন, এবং
- পপ করা বন্ধনীটি এর প্রারম্ভিক বন্ধনীর সাথে সম্পর্কিত কিনা তা পরীক্ষা করুন
- বর্তমান অক্ষর, তাহলে এটি ঠিক আছে, অন্যথায়, এটি ভারসাম্যপূর্ণ নয়।
- স্ট্রিং ফুরিয়ে যাওয়ার পর, যদি স্ট্যাকের মধ্যে কিছু প্রারম্ভিক বন্ধনী অবশিষ্ট থাকে, তাহলে স্ট্রিংটি ভারসাম্যপূর্ণ নয়।
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#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
