मान लीजिए हमारे पास एक अभिव्यक्ति है। अभिव्यक्ति में कुछ पैरेंथेसिस हैं; हमें जांचना है कि पैरेंथेसिस संतुलित (balanced) हैं या नहीं। पैरेंथेसिस का क्रम (), {} और [] है। मान लीजिए दो स्ट्रिंग हैं। "()[(){()}]" यह वैध है, लेकिन "{[}]" अवैध है।
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- अभिव्यक्ति को तब तक पार करें जब तक यह समाप्त न हो जाए:
- यदि वर्तमान वर्ण प्रारंभिक ब्रैकेट है जैसे (, { या [, तो स्टैक में पुश करें
- यदि वर्तमान वर्ण समापन ब्रैकेट है जैसे ), } या ], तो स्टैक से पॉप करें, और
- जांचें कि क्या पॉप किया गया ब्रैकेट वर्तमान वर्ण का संगत प्रारंभिक ब्रैकेट है, तो यह ठीक है, अन्यथा, यह संतुलित नहीं है।
- स्ट्रिंग समाप्त होने के बाद, यदि स्टैक में कुछ प्रारंभिक ब्रैकेट बचे हैं, तो स्ट्रिंग संतुलित नहीं है।
उदाहरण (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 << "यह संतुलित अभिव्यक्ति है";
else
cout << "यह असंतुलित अभिव्यक्ति है";
}
इनपुट
"()[(){()}]"
आउटपुट
यह संतुलित अभिव्यक्ति है
