C ++平衡表达与替换

括号的平衡表达式是按正确的顺序包含所有括号对的表达式，这意味着对于每个开括号，都有一个括号，括号的正确顺序即{}。

让我们举几个例子来更好地理解这个概念-

表达式-{{[[] [] {}）（{} [] {}）}

输出-平衡

解释-我们可以看到，对于每个开头括号，都有一个结尾括号。成对的所有位于开括号和闭括号之间的括号。

输出-不平衡

解释-有一些成对的括号使表达式不平衡。

在这个称为带有替换的余额表达式的问题中，我们得到了一个字符串，其中包含这些括号'{'，'}'，'['，']'，'（'，'）'的表达式。在某些地方缺少括号，并用“ *”代替。而且，我们必须检查天气情况，以适当的方括号替换所有星号符号是否可以使给定表达式能够变为有效表达式。

例

输入 − exp =“ {[*（*）]}”

输出 -表达式可以平衡

说明 -有两个符号需要替换。并且在替换后将变成{[（（()）]}

输入 − exp =“ [（*）{} {{}}]”

输出 -表达式无法平衡

说明-有一个符号需要替换。并且在用任意括号替换*时，表达式无法平衡。

现在，由于我们对问题有了清楚的了解，因此可以为该问题生成解决方案。为了检查给定的括号表达式是否平衡，我们将使用堆栈数据结构来执行任务。

为完成此任务而执行的操作是-

• 遍历字符串表达式的每个元素，然后执行-

• 当在表达式中遇到开括号，即'{'，'['，'（'时，将元素推入堆栈。

• 当在表达式中遇到一个右括号时，即'}'，']'，'）'。弹出堆栈顶部的元素，然后检查这是否与遇到的右括号匹配。

• 如果两个括号都匹配，则移至表达式的下一个元素（步骤1）。

• 如果两个括号都不匹配，则表达式不平衡。

• 在表达式中遇到*时，它可以是开括号也可以是右括号。然后，

• 首先将其视为左括号，然后将其推入堆栈，并使用递归调用下一个元素找到匹配的右括号。如果这导致麻烦，请继续执行下一步

• 将其视为右括号，它必须与堆栈顶部匹配，然后弹出堆栈顶部。

• *的收盘价与不平衡的开盘收益不匹配。

• 根据结果打印语句。

示例

基于此解决方案，让我们创建一个程序

#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b){
   if ((a == '{' &amp; b == '}') || (a == '[' &amp; b == ']') || (a == '(' &amp; b == ')') || a == '*')
      return 1;
   return 0;
}
int isBalancedexpression(string s, stack<char> 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<char> 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