C++ 从表达式中删除无效的括号
给定一个括号序列；现在，您必须通过删除无效括号来打印所有可能的括号，例如
输入： str = “()())()” - 输出： ()()() (())() There are two possible solutions "()()()" and "(())()" 输入： 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; //如果我们检查那个刺，所以我们把它放在访问中
//这样我们就不会再遇到那个字符串
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++程序以及解决此问题的完整方法(Normal)。我们可以用其他语言编写相同的程序，例如C、java、python和其他语言。我们希望本教程对您有所帮助。