C++ 从表达式中删除无效括号
c++server side programmingprogramming
给定一个括号序列；现在，您必须通过删除无效括号来打印所有可能的括号，例如
输入:str = “()())()” - 输出:()()() (())() 有两种可能的解决方案 "()()()" 和 "(())()" 输入:str = (v)())() 输出:(v)()() (v())()
在这个问题中，我们将使用回溯，以便打印所有有效序列。
寻找解决方案的方法
在这种方法中，我们将尝试使用 BFS 逐个删除左括号和右括号。现在，对于每个序列，我们检查它是否有效。如果有效，则将其打印为输出。
示例
#include <bits/stdc++.h>
using namespace std;
bool isParenthesis(char c){
return ((c == '(') || (c == ')'));
}
bool validString(string str){
// cout << str << " ";
int cnt = 0;
for (int i = 0; i < str.length(); i++){
if (str[i] == '(')
cnt++;
else if (str[i] == ')')
cnt--;
if (cnt < 0)
return false;
}
// cout << str << &" &";;
return (cnt == 0);
}
void validParenthesesSequences(string str){
if (str.empty())
return ;
set<string> visit; // 如果我们检查了该字符串，则将其放入 visit 中
// 这样我们就不会再次遇到该字符串
queue<string> q; // 执行 bfs 的队列
string temp;
bool level;
// 将给定的字符串作为起始节点推送到队列中
q.push(str);
visit.insert(str);
while (!q.empty()){
str = q.front(); q.pop();
if (validString(str)){
// cout << &"s";
cout << str << &";\n"; // 我们打印字符串
level = true; // 因为我们在同一级别上找到了字符串，所以我们不需要从中应用 bfs
}
if (level)
continue;
for (int i = 0; i < str.length(); i++){
if (!isParenthesis(str[i])) // 我们不会从字符串中删除括号以外的任何其他字符
continue;
temp = str.substr(0, i) + str.substr(i + 1); // 从字符串中逐个删除括号
if (visit.find(temp) == visit.end()) { // 如果我们检查该字符串，则不会再次检查它
q.push(temp);
visit.insert(temp);
}
}
}
}
int main(){
string s1;
s1 = "(v)())()";
cout << "输入:" << s1 << "\n";
cout << "输出:";
validParenthesesSequences(s1);
return 0;
}
输出
输入:(v)())() 输出:(v())()
上述代码的解释
在上述方法中，我们只需逐个删除括号即可。现在，我们可以像删除括号一样删除括号。我们还会跟踪先前的序列，这样我们就不会检查相同的序列两次。现在，如果我们在所有可能性中找到一个有效序列，我们会打印所有有效可能性，这就是我们的程序的运行方式。
结论
在本教程中，我们解决了一个问题，即删除无效括号。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法(正常)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。我们希望本教程对您有所帮助。
