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