अवधारणा
दिए गए स्ट्रिंग str जिसमें वर्ण '(', ')', '{', '}', '[' और ']' हैं, यह पता लगाना है कि ब्रैकेट संतुलित हैं या नहीं।
ब्रैकेट संतुलित माने जाते हैं यदि:
- खुले ब्रैकेट को उसी प्रकार के ब्रैकेट से बंद किया जाना चाहिए।
- खुले ब्रैकेट को सही क्रम में बंद किया जाना चाहिए।
उदाहरण
इनपुट - str = "(()){}"
आउटपुट - Yes
इनपुट - str = "))(([]["
आउटपुट - No
विधि
- दो चर a और b निर्दिष्ट करें ताकि तुलना किए जाने वाले दो ब्रैकेट को ट्रैक किया जा सके।
- एक काउंट बनाए रखें जिसका मान खुले ब्रैकेट मिलने पर बढ़ता है और बंद ब्रैकेट मिलने पर घटता है।
- खुले ब्रैकेट मिलने पर b = a, a = a + 1 और count = count + 1 निर्दिष्ट करें।
- जब बंद ब्रैकेट मिलते हैं तो काउंट घटाएं और i और j पर ब्रैकेट की तुलना करें:
- यदि a और b पर ब्रैकेट मेल खाते हैं, तो स्ट्रिंग में a-वें और b-वें स्थान पर '#' डालें। a को बढ़ाएं और b को घटाएं जब तक गैर-'#' मान न मिल जाए या b >= 0।
- यदि a और b पर ब्रैकेट मेल नहीं खाते तो गलत लौटाएं।
- यदि count != 0 तो गलत लौटाएं।
C++ कार्यान्वयन
// 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;
}
}
int main(){
string str1 = "[[]][]()";
if (isValid(str1))
cout << "Yes";
else
cout << "No";
return 0;
}आउटपुट
Yes
