假设我们有一个表达式。该表达式带有一些括号;我们必须检查括号是否平衡。括号的顺序是(),{}和[]。假设有两个字符串。“()[(){()}]”有效,但“ {[}]”无效。
任务很简单;我们将使用堆栈来做到这一点。我们应该按照以下步骤获得解决方案-
遍历表达式,直到用尽为止
如果当前字符是用(,{或[
如果当前字符是右括号,如},}或],则从堆栈中弹出,并检查弹出的括号是否与当前字符的起始括号相对应,就可以了,否则就不平衡了。
字符串用尽后,如果堆栈中还剩下一些起始括号,则说明该字符串不平衡。
#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