পরেনথেসিসের একটি সমতুল্য অভিব্যক্তি হলো এমন অভিব্যক্তি যেখানে সব ধরনের পরেনথেসিস সঠিক ক্রমে জোড়ায় থাকে। অর্থাৎ, প্রতিটি ওপেনিং পরেনথেসিসের জন্য একটি ক্লোজিং পরেনথেসিস সঠিক ক্রমে থাকে, যেমন { }।
কিছু উদাহরণ দিয়ে বুঝি:
অভিব্যক্তি: {([][]{})({}[]{})}
আউটপুট: balanced
ব্যাখ্যা: প্রতিটি ওপেনিং পরেনথেসিসের জন্য একটি ক্লোজিং পরেনথেসিস রয়েছে। সব পরেনথেসিস একটি ওপেনিং এবং ক্লোজিং পরেনথেসিসের মাঝপথে জোড়ায় থাকছে।
আউটপুট: not balance
ব্যাখ্যা: কিছু অक्रमিক জোড়া পরেনথেসিস রয়েছে যা অভিব্যক্তিকে অসমতুল্য করে।
ব্যালেন্সড অভিব্যক্তি উইথ রিপ্লেসমেন্ট সমস্যায়, একটি স্ট্রিং দেওয়া থাকে যাতে '{', '}', '[', ']', '(', ')' ব্র্যাকেটগুলো থাকে। কিছু জায়গায় ব্র্যাকেট নেই এবং তার জায়গায় "*" চিহ্ন আছে। সব "*" কে উপযুক্ত ব্র্যাকেট দিয়ে রিপ্লেস করলে কি অভিব্যক্তিটি বৈধ (valid) হতে পারে, তা যাচাই করতে হবে।
উদাহরণ:
Input: exp = "{[*(*)]}"
Output: the expression can be balanced
ব্যাখ্যা: দুটি চিহ্ন রিপ্লেস করতে হবে। রিপ্লেস করলে হবে {[(())]}
Input: exp = "[(*){}{{}}]"
Output: the expression cannot be balanced
ব্যাখ্যা: একটি চিহ্ন রিপ্লেস করতে হবে। "*" কে যেকোনো ব্র্যাকেট দিয়ে রিপ্লেস করলেও অভিব্যক্তি সমতুল্য হয় না।
সমস্যা বুঝতে পারার পর সমাধান বানানো যাক। দেওয়া পরেনথেসিস অভিব্যক্তি সমতুল্য কিনা যাচাই করতে স্ট্যাক (stack) ডেটা স্ট্রাকচার ব্যবহার করা হবে।
কাজ সম্পন্ন করার অপারেশনগুলো:
স্ট্রিং অভিব্যক্তির প্রতিটি উপাদান ঘুরে নিচের কাজগুলো করা:
যখন ওপেনিং ব্র্যাকেট পাওয়া যায় ({, [, (), সেটি স্ট্যাকে পুশ করা।
যখন ক্লোজিং ব্র্যাকেট পাওয়া যায় (}, ], )), স্ট্যাকের টপ এলিমেন্ট পপ করে মিল যাচাই করা।
যদি জোড়া মিলে, পরবর্তী উপাদানে যাওয়া (স্টেপ ১)।
যদি না মিলে, অভিব্যক্তি not balanced।
যখন "*" পাওয়া যায়, যা ওপেনিং ও ক্লোজিং উভয় হতে পারে। তখন:
প্রথমে এটিকে ওপেনিং ব্র্যাকেট ধরে স্ট্যাকে পুশ করে রিকারসিভ কল দিয়ে মিল খুঁজা। যদি ফাল্স হয়, পরবর্তী স্টেপ।
এটিকে ক্লোজিং ব্র্যাকেট ধরে, স্ট্যাকের টপের সাথে মিল যাচাই করা। মিললে পপ।
যদি "*" এর ক্লোজিং ভ্যালু কোনো ওপেনিংয়ের সাথে না মিলে, "not balanced" রিটার্ন।
ফলাফল অনুযায়ী স্টেটমেন্ট প্রিন্ট করা।
উদাহরণ
এই সমাধান অনুযায়ী প্রোগ্রাম তৈরি করা যাক:
#include <bits/stdc++.h> using namespace std; int isMatching(char a, char b){ if ((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == '*') return 1; return 0; } int isBalancedexpression(string s, stack ele, int ind){ if (ind == s.length()) return ele.empty(); char topEle; int res; if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') { ele.push(s[ind]); return isBalancedexpression(s, ele, ind + 1); } else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') { if (ele.empty()) return 0; topEle = ele.top(); ele.pop(); if (!isMatching(topEle, s[ind])) return 0; return isBalancedexpression(s, ele, ind + 1); } else if (s[ind] == '*') { stack tmp = ele; tmp.push(s[ind]); res = isBalancedexpression(s, tmp, ind + 1); if (res) return 1; if (ele.empty()) return 0; ele.pop(); return isBalancedexpression(s, ele, ind + 1); } } int main(){ string s = "{[*(*)]}"; stack ele; if (isBalancedexpression(s, ele, 0)) cout << "Balanced"; else cout << "Not Balanced"; return 0; } আউটপুট
Balanced
