अवधारणा
'(', ')', '{', '}', '[' और ']' वर्णों वाली एक स्ट्रिंग स्ट्रिंग दिए जाने के संबंध में, कार्य यह पता लगाना है कि कोष्ठक संतुलित हैं या नहीं।
कोष्ठकों को संतुलित के रूप में निरूपित किया जाता है यदि -
-
हम खुले कोष्ठकों को बंद करते हैं और उन्हें उसी प्रकार के कोष्ठकों द्वारा बंद किया जाना चाहिए।
-
फिर से हम खुले कोष्ठकों को सही क्रम के अनुसार बंद करते हैं।
इनपुट - str ="(()){}"
आउटपुट - हाँ
इनपुट - str ="))(([]["
आउटपुट - नहीं
विधि
-
तुलना करने के लिए दो कोष्ठकों का ट्रैक रखने के लिए दो चर a और b असाइन करें।
-
एक गिनती को बनाए रखा जाना चाहिए जिसका मूल्य वृद्धि एक समापन ब्रैकेट का सामना करने पर और घटते ब्रैकेट का सामना करने पर बढ़ता है।
-
ओपनिंग ब्रैकेट मिलने पर b =a, a =a + 1 और count=count+1 असाइन करें।
-
उस समय जब क्लोजिंग ब्रैकेट्स का सामना करना पड़ता है, घटती संख्या और i और j पर ब्रैकेट्स की तुलना करें,
-
यदि यह देखा गया है कि a और b पर कोष्ठक एक मेल हैं, तो स्ट्रिंग में '#' को वें और b वें स्थान पर प्रतिस्थापित करें। a को बढ़ाया जाता है और b को तब तक घटाया जाता है जब तक कि गैर '#' मान सामने न आ जाए या b ≥ 0.
-
यदि यह देखा गया है कि a और b पर कोष्ठक मेल नहीं खाते हैं, तो गलत लौटें।
-
-
अगर गिनती!=0 तो झूठी वापसी करें।
उदाहरण
// 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