मान लीजिए कि हमारे पास एक व्यंजक है। व्यंजक के कुछ कोष्ठक हैं; हमें यह जांचना है कि कोष्ठक संतुलित हैं या नहीं। कोष्ठकों का क्रम (), {} और [] है। मान लीजिए कि दो तार हैं। "()[(){()}]" यह मान्य है, लेकिन "{[}]" अमान्य है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- व्यंजक को तब तक पार करें जब तक वह समाप्त न हो जाए
- यदि वर्तमान वर्ण ब्रैकेट खोल रहा है जैसे (, { या [, तो स्टैक में पुश करें
- यदि वर्तमान वर्ण ब्रैकेट बंद कर रहा है जैसे ), } या ], तो स्टैक से पॉप करें, और
- जांचें कि क्या पॉप किया गया ब्रैकेट संबंधित प्रारंभिक ब्रैकेट है या नहीं
- वर्तमान चरित्र, तो ठीक है, अन्यथा, वह संतुलित नहीं है।
- स्ट्रिंग समाप्त होने के बाद, यदि स्टैक में कुछ शुरुआती ब्रैकेट बचे हैं, तो स्ट्रिंग संतुलित नहीं है।
उदाहरण(C++)
बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -
#include <iostream>
#include <stack>
using namespace std;
bool isBalancedExp(string exp) {
stack<char> stk;
char x;
for (int i=0; i<exp.length(); i++) {
if (exp[i]=='('||exp[i]=='['||exp[i]=='{') {
stk.push(exp[i]);
continue;
}
if (stk.empty())
return false;
switch (exp[i]) {
case ')':
x = stk.top();
stk.pop();
if (x=='{' || x=='[')
return false;
break;
case '}':
x = stk.top();
stk.pop();
if (x=='(' || x=='[')
return false;
break;
case ']':
x = stk.top();
stk.pop();
if (x =='(' || x == '{')
return false;
break;
}
}
return (stk.empty());
}
int main() {
string expresion = "()[(){()}]";
if (isBalancedExp(expresion))
cout << "This is Balanced Expression";
else
cout << "This is Not Balanced Expression";
} इनपुट
"()[(){()}]" आउटपुट
This is Balanced Expression