কনসেপ্ট
দেওয়া স্ট্রিং str-এ '(', ')', '{', '}', '[', ']' ক্যারেক্টার থাকলে ব্র্যাকেটগুলো ব্যালেন্সড কিনা তা খুঁজে বের করুন।
ব্র্যাকেটগুলো ব্যালেন্সড যদি:
- খোলা ব্র্যাকেটগুলো একই টাইপের ব্র্যাকেট দিয়ে বন্ধ হয়।
- খোলা ব্র্যাকেটগুলো সঠিক অর্ডারে বন্ধ হয়।
ইনপুট − str = "(()){}"
আউটপুট − Yes
ইনপুট − str = "))(([]["
আউটপুট − No
পদ্ধতি
- দুটি ভেরিয়েবল a এবং b রাখুন দুটি ব্র্যাকেট কমপেয়ার করার জন্য।
- একটি কাউন্ট রাখুন যা খোলা ব্র্যাকেটে বাড়বে এবং বন্ধ ব্র্যাকেটে কমবে।
- খোলা ব্র্যাকেট পাওয়া গেলে b=a, a=a+1, count++ করুন।
- বন্ধ ব্র্যাকেট পাওয়া গেলে count-- করুন এবং i ও j ইন্ডেক্সের ব্র্যাকেট কমপেয়ার করুন:
- যদি a এবং b-র ব্র্যাকেট ম্যাচ করে, স্ট্রিংয়ে '#' বসিয়ে a বাড়ান এবং b কমান যতক্ষণ না '#' না পাওয়া যায় বা b >= 0।
- যদি ম্যাচ না করে, false রিটার্ন করুন।
- শেষে count != 0 হলে false রিটার্ন করুন।
উদাহরণ
#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;
}
}
int main(){
string str1 = "[[]][]()";
if (isValid(str1))
cout << "Yes";
else
cout << "No";
return 0;
} আউটপুট
Yes
