हमें कोष्ठक युक्त एक स्ट्रिंग दी गई है और कार्य कोष्ठक अनुक्रमों के युग्मों की गणना करना है जिन्हें इस प्रकार बनाया जा सकता है कि कोष्ठक संतुलित हों।
कोष्ठकों को संतुलित कहा जाता है जब उद्घाटन और समापन कोष्ठक की संख्या समान होती है। एक बार उपयोग किए गए कोष्ठकों को युग्म बनाने के लिए दो बार नहीं माना जा सकता है।
इनपुट - स्ट्रिंग पैरान [] ={ ")() ())", "(", ")(", ")(", ")" }
आउटपुट − कोष्ठक अनुक्रमों के जोड़े की संख्या जैसे कि कोष्ठक संतुलित हैं:1
स्पष्टीकरण - हम गिनती की बेहतर गणना करने के लिए स्ट्रिंग के हर सेट को लेंगे। आइए पहले तत्व को ") () ()) के रूप में लें, जिसमें 4 क्लोजिंग ब्रैकेट और 2 ओपनिंग ब्रैकेट हैं, इसलिए हम स्ट्रिंग में अगले एलिमेंट की तलाश करेंगे, जिसमें एक संतुलित कोष्ठक अनुक्रम बनाने के लिए बिल्कुल 2 क्लोजिंग ब्रैकेट हों, जो कि नहीं है। वहाँ स्ट्रिंग में तो हम इसे त्याग देंगे और अगले के लिए जाएंगे। तो समान उद्घाटन और समापन कोष्ठक के साथ मान्य जोड़ी (2, 5) पर है इसलिए गिनती 1 है।
इनपुट - स्ट्रिंग पैरान [] ={ ")() ())", "((", "(", ") (", ") (", ")"}
आउटपुट − कोष्ठक अनुक्रमों के जोड़े की संख्या जैसे कि कोष्ठक संतुलित हैं:1
स्पष्टीकरण - वैध संतुलित कोष्ठक जोड़े (1, 2) और (3, 6) पर हैं। इसलिए गिनती 2 है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
स्ट्रिंग इनपुट करें और लंबाई () फ़ंक्शन का उपयोग करके स्ट्रिंग की लंबाई की गणना करें और डेटा को आगे की प्रक्रिया के लिए कार्य करने के लिए पास करें।
-
कोष्ठकों के मान्य युग्मों को संग्रहीत करने के लिए एक अस्थायी चर गणना लें और unordered_map प्रकार का एक um_1 और um_2 चर बनाएं।
-
0 से एक स्ट्रिंग के आकार तक के लिए एक और लूप प्रारंभ करें
-
लूप के अंदर, str को परान के रूप में सेट करें [i] यानी कोष्ठक का पहला तत्व और फिर से एक स्ट्रिंग की लंबाई की गणना करें।
-
एक अस्थायी चर को पहले और अंतिम के रूप में लें और उन्हें 0
. के साथ प्रारंभ करें -
स्ट्रिंग की लंबाई तक j से 0 तक के लिए एक और लूप प्रारंभ करें
-
लूप के अंदर, IF str[j] ='(' की जाँच करें, फिर पहले को 1 से बढ़ाएँ ELSE जाँच करें IF पहले =1 फिर पहले को 1 से घटाएँ ELSE अंतिम को 1 से बढ़ाएँ।
-
अब जांचें कि IF पहले 1 है और अंतिम 0 है, फिर um_1 [प्रथम] ++ सेट करें और जांचें कि IF अंतिम 1 है और पहले 0 है, फिर um_2 [lst] ++ सेट करें और IF पहले 0 है और अंतिम भी 0 है, फिर गिनती बढ़ाएं द्वारा 1.
-
गिनती को गिनती के रूप में सेट करें / 2
-
लूप को 0 से um_1 तक प्रारंभ करें और गणना को um_1.second और um_2.first
से न्यूनतम मान के रूप में सेट करें -
गिनती लौटाएं
-
परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int parentheses(string paran[], int size){
int count = 0;
unordered_map<int, int> um_1, um_2;
for (int i = 0; i < size; i++){
string str = paran[i];
int len = str.length();
int first = 0;
int last = 0;
for (int j = 0; j < len; j++){
if (str[j] == '('){
first++;
}
else{
if (first==1){
first--;
}
else{
last++;
}
}
}
if(first==1 && last!=1){
um_1[first]++;
}
if (last==1 && first!=1){
um_2[last]++;
}
if(first!=1 && last!=1){
count++;
}
}
count = count / 2;
for (auto it : um_1){
count += min(it.second, um_2[it.first]);
}
return count;
}
int main(){
string paran[] = { ")()())", "(", ")(", ")(", ")"};
int size = sizeof(paran) / sizeof(paran[0]);
cout<<"Count of pairs of parentheses sequences such that parentheses are balanced are:
"<<parentheses(paran, size);
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of pairs of parentheses sequences such that parentheses are balanced are: 1