C ++中的有效括号字符串

假设我们有一个表达式。该表达式带有一些括号;我们必须检查括号是否平衡。括号的顺序是(),{}和[]。假设有两个字符串。“()[(){()}]”有效,但“ {[}]”无效。

为了解决这个问题,我们将遵循以下步骤-

  • 遍历表达式,直到用尽为止

    • 如果当前字符是用(,{或[

    • 如果当前字符是右括号,如},}或],则从堆栈弹出,然后

    • 检查弹出的括号是否对应于

    • 当前字符,那很好,否则,那是不平衡的。

  • 字符串用尽后,如果堆栈中还剩下一些起始括号,则说明该字符串不平衡。

例子(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