कोष्ठक का एक संतुलित अभिव्यक्ति एक ऐसा अभिव्यक्ति है जिसमें सभी प्रकार के कोष्ठक सही क्रम में एक साथ होते हैं। इसका अर्थ है कि प्रत्येक प्रारंभिक कोष्ठक के लिए एक समापन कोष्ठक होता है जो कोष्ठक के उचित क्रम में होता है यानी { }।
आइए कुछ उदाहरण लेकर अवधारणा को बेहतर ढंग से समझते हैं:
अभिव्यक्ति - {([][]{})({}[]{})}
आउटपुट - संतुलित
व्याख्या - हम देख सकते हैं कि प्रत्येक प्रारंभिक कोष्ठक के लिए एक समापन कोष्ठक है। एक प्रारंभिक कोष्ठक और समापन कोष्ठक के बीच के सभी कोष्ठक जोड़े में हैं।
आउटपुट - असंतुलित
व्याख्या - कुछ अव्यवस्थित जोड़े हैं जो अभिव्यक्ति को असंतुलित बनाते हैं।
प्रतिस्थापन के साथ संतुलित अभिव्यक्ति नामक इस समस्या में, हमें एक स्ट्रिंग दी गई है जिसमें इन कोष्ठकों का एक अभिव्यक्ति है: '{', '}', '[', ']', '(', ')'। कुछ स्थान ऐसे हैं जहां कोष्ठक गायब हैं और उनके स्थान पर "*" रखा गया है। और हमें जांचना है कि क्या सभी एस्टेरिस्क प्रतीकों को उपयुक्त कोष्ठक से बदलने पर दी गई अभिव्यक्ति एक वैध अभिव्यक्ति बन सकती है।
उदाहरण
इनपुट - exp = "{[*(*)]}"
आउटपुट - अभिव्यक्ति संतुलित हो सकती है
व्याख्या - दो प्रतीक हैं जिन्हें बदलने की आवश्यकता है। और प्रतिस्थापन पर यह {[(())]} बन जाएगा।
इनपुट - exp = "[(*){}{{}}]"
आउटपुट - अभिव्यक्ति संतुलित नहीं हो सकती
व्याख्या - एक प्रतीक है जिसे बदलने की आवश्यकता है। और * को किसी भी कोष्ठक से बदलने पर अभिव्यक्ति संतुलित नहीं हो सकती।
अब चूंकि हमें समस्या की स्पष्ट समझ है, हम इस समस्या के लिए एक समाधान उत्पन्न कर सकते हैं। यह जांचने के लिए कि दी गई कोष्ठक अभिव्यक्ति संतुलित होगी या नहीं, हम स्टैक डेटा संरचना का उपयोग करेंगे।
इस कार्य को पूरा करने के लिए किए गए ऑपरेशन हैं:
स्ट्रिंग अभिव्यक्ति के प्रत्येक तत्व को पार करें और करें:
जब अभिव्यक्ति में एक प्रारंभिक कोष्ठक मिलता है यानी '{', '[', '(', तो तत्व को स्टैक में पुश करें।
जब अभिव्यक्ति में एक समापन कोष्ठक मिलता है यानी '}', ']', ')'। स्टैक के शीर्ष पर तत्व को पॉप करें और जांचें कि क्या यह मिले समापन कोष्ठक के लिए एक मिलान प्रारंभिक है।
यदि दोनों कोष्ठक मेल खाते हैं, तो अभिव्यक्ति के अगले तत्व पर जाएं (चरण 1)।
यदि दोनों कोष्ठक मेल नहीं खाते, तो अभिव्यक्ति संतुलित नहीं है।
जब अभिव्यक्ति में * मिलता है जो प्रारंभिक और साथ ही समापन कोष्ठक हो सकता है। तब,
पहले इसे प्रारंभिक कोष्ठक मानें और इसे स्टैक में पुश करें और पुनरावर्ती कॉल का उपयोग करके अगले तत्व के लिए मिलान समापन कोष्ठक ढूंढें। यदि इसका परिणाम गलत है, तो अगले चरण का पालन करें।
इसे समापन कोष्ठक मानें, यह स्टैक के शीर्ष से मेल खाना चाहिए फिर स्टैक के शीर्ष को पॉप करें।
यदि * का समापन मान किसी प्रारंभिक से मेल नहीं खाता तो असंतुलित लौटाएं।
परिणाम के आधार पर कथन प्रिंट करें।
उदाहरण
इस समाधान के आधार पर आइए एक प्रोग्राम बनाते हैं
#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b) {
if ((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == '*')
return 1;
return 0;
}
int isBalancedexpression(string s, stack ele, int ind) {
if (ind == s.length())
return ele.empty();
char topEle;
int res;
if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
ele.push(s[ind]);
return isBalancedexpression(s, ele, ind + 1);
}
else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
if (ele.empty())
return 0;
topEle = ele.top();
ele.pop();
if (!isMatching(topEle, s[ind]))
return 0;
return isBalancedexpression(s, ele, ind + 1);
}
else if (s[ind] == '*') {
stack tmp = ele;
tmp.push(s[ind]);
res = isBalancedexpression(s, tmp, ind + 1);
if (res)
return 1;
if (ele.empty())
return 0;
ele.pop();
return isBalancedexpression(s, ele, ind + 1);
}
}
int main() {
string s = "{[*(*)]}";
stack ele;
if (isBalancedexpression(s, ele, 0))
cout << "Balanced";
else
cout << "Not Balanced";
return 0;
}
आउटपुट
Balanced
