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