数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ 带替换的平衡表达式
括号的平衡表达式是指包含所有类型括号的配对，且顺序正确的表达式。这意味着每个左括号都有一个对应的右括号，并且括号的顺序正确，例如 { }。
让我们来看几个例子，以便更好地理解这个概念：
表达式 − {([][]{})({}[]{})}
输出 − 平衡
解释 − 我们可以看到，每个左括号都有一个对应的右括号。所有位于一对左括号和右括号之间的括号都是成对的。
输出 − 不平衡
解释 − 有一些括号的顺序不对，使得表达式不平衡。
在这个被称为“带替换的平衡表达式”的问题中，我们得到一个字符串，其中包含这些括号 ‘{’ , ‘}’ , ‘[’ , ‘]’ , ‘(’ , ‘)’ 。有些地方缺少括号，用“*”代替。我们必须检查是否可以通过用合适的括号替换所有星号符号，使给定的表达式成为有效的表达式。
示例
输入 − exp = “{[*(*)]}”
输出 − 表达式可以平衡
解释 − 有两个符号需要替换。替换后将变成 {[(())]}。
输入 − exp = “[(*){}{{}}]”
输出 − 表达式无法平衡
解释 − 有一个符号需要替换。用任何括号替换 * 后，表达式都无法平衡。
现在，既然我们对问题有了清晰的理解，我们可以为这个问题生成一个解决方案。为了检查给定的括号表达式是否平衡，我们将使用堆栈数据结构来执行我们的任务。
为了完成此任务而执行的操作是：
遍历字符串表达式的每个元素并执行：
当在表达式中遇到左括号，即 ‘{’ , ‘[’ , ‘(’ 时，将元素压入堆栈。
当在表达式中遇到右括号，即 ‘}’ , ‘]’ , ‘)’ 时，弹出堆栈顶部的元素，并检查这是否是遇到的右括号对应的左括号。
如果两个括号匹配，则移动到表达式的下一个元素（步骤 1）。
如果两个括号不匹配，则表达式不平衡。
当在表达式中遇到 * 时，它可以是左括号也可以是右括号。然后：
首先将其视为左括号并将其压入堆栈，并使用递归调用为下一个元素查找匹配的右括号。如果结果为假，则执行下一步
将其视为右括号，它必须与堆栈顶部匹配，然后弹出堆栈顶部。
如果 * 的右括号与左括号不匹配，则返回不平衡。
根据结果打印语句。
示例
基于此解决方案，让我们创建一个程序
#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b){
if ((a == '{' & b == '}') || (a == '[' & b == ']') || (a == '(' & 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
318 次查看
