ধারণা
'(', ')', '{', '}', '[' এবং ']' অক্ষর সম্বলিত একটি স্ট্রিং স্ট্রের ক্ষেত্রে, কাজটি হল বন্ধনীগুলি ভারসাম্যপূর্ণ কিনা তা খুঁজে বের করা৷
বন্ধনীগুলিকে সুষম হিসাবে চিহ্নিত করা হয় যদি −
-
আমরা খোলা বন্ধনী বন্ধ করি একই ধরনের বন্ধনী দ্বারা বন্ধ করা আবশ্যক।
-
আবার আমরা সঠিক ক্রম অনুসারে খোলা বন্ধনী বন্ধ করি।
ইনপুট − str =“(()){}”
আউটপুট - হ্যাঁ
ইনপুট − str =“))(([][”
)আউটপুট - না
পদ্ধতি
-
তুলনা করার জন্য দুটি বন্ধনীর ট্র্যাক রাখতে দুটি ভেরিয়েবল a এবং b বরাদ্দ করুন।
-
একটি গণনা বজায় রাখা উচিত যার মান ওপেনিং ব্র্যাকেটের মুখোমুখি হওয়ার সময় বৃদ্ধি পায় এবং একটি বন্ধ বন্ধনীর সম্মুখীন হলে হ্রাস পায়৷
-
বন্ধনী খোলার সময় b =a, a =a + 1 এবং count=count+1 বরাদ্দ করুন।
-
যে সময়ে বন্ধনী বন্ধনীর সংখ্যা হ্রাসের সম্মুখীন হয় এবং i এবং j এ বন্ধনী তুলনা করুন,
-
যদি দেখা যায় যে a এবং b তে বন্ধনী একটি মিল, তাহলে একটি তম এবং b তম অবস্থানে স্ট্রিং এ '#' বিকল্প করুন। a বর্ধিত হয় এবং b হ্রাস করা হয় যতক্ষণ না '#' মান না আসে বা b ≥ 0 না হয়।
-
যদি দেখা যায় যে a এবং b তে বন্ধনী মিলছে না তাহলে মিথ্যা ফেরত দিন।
-
-
গণনা হলে!=0 তারপর মিথ্যা ফেরত দিন।
উদাহরণ
নেমস্পেস std;bool helperFunc (int&count1, string&s1, int&i1, int&j1, char tocom1) ব্যবহার করে// C++ implementation of the approach #include <iostream> using namespace std; bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){ count1--; if (j1 > -1 && s1[j1] == tocom1) { s1[i1] = '#'; s1[j1] = '#'; while (j1 >= 0 && s1[j1] == '#') j1--; i1++; return 1; } else return 0; } bool isValid(string s1){ if (s1.length() == 0) return true; else { int i1 = 0; int count1 = 0; int j1 = -1; bool result1; while (i1 < s1.length()) { switch (s1[i1]) { case '}': result1 = helperFunc(count1, s1, i1, j1, '{'); if (result1 == 0) { return false; } break; case ')': result1 = helperFunc(count1, s1, i1, j1, '('); if (result1 == 0) { return false; } break; case ']': result1 = helperFunc(count1, s1, i1, j1, '['); if (result1 == 0) { return false; } break; default: j1 = i1; i1++; count1++; } } if (count1 != 0) return false; return true; } } // Driver code int main(){ string str1 = "[[]][]()"; if (isValid(str1)) cout << "Yes"; else cout << "No"; return 0; }
আউটপুট
Yes