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