数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 删除表达式中无效的括号
给定一个括号序列；现在，您必须打印所有可能的括号，可以通过删除无效括号来生成，例如
Input : str = “()())()” - Output : ()()() (())() There are two possible solutions "()()()" and "(())()" Input : str = (v)())() Output : (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; // if we checked that sting so we put it inside visit
// so that we will not encounter that string again
queue<string> q; // queue for performing bfs
string temp;
bool level;
// pushing given string as starting node into queue
q.push(str);
visit.insert(str);
while (!q.empty()){
str = q.front(); q.pop();
if (validString(str)){
// cout << "s";
cout << str << "\n"; // we print our string
level = true; // as we found the sting on the same level so we don't need to apply bfs from it
}
if (level)
continue;
for (int i = 0; i < str.length(); i++){
if (!isParenthesis(str[i])) // we won't be removing any other characters than the brackets from our string
continue;
temp = str.substr(0, i) + str.substr(i + 1); // removing parentheses from the strings one by one
if (visit.find(temp) == visit.end()) { // if we check that string so we won't check it again
q.push(temp);
visit.insert(temp);
}
}
}
}
int main(){
string s1;
s1 = "(v)())()";
cout << "Input : " << s1 << "\n";
cout << "Output : ";
validParenthesesSequences(s1);
return 0;
}输出
Input : (v)())() Output : (v())()
上述代码的解释
在上述方法中，我们简单地一一删除括号，并且在我们删除括号的同时，我们也跟踪之前的序列，这样我们就不会两次检查同一个序列。如果我们从所有这些可能性中找到一个有效的序列，我们将打印所有有效的可能性，这就是我们的程序的执行过程。
结论
在本教程中，我们解决了一个问题，即查找并删除无效括号。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法（常规方法）。我们可以使用 C、Java、Python 等其他语言编写相同的程序。希望您觉得本教程有所帮助。
更新于：2021年11月26日
180 次浏览
广告