C++ 删除表达式中无效的括号


给定一个括号序列;现在,您必须打印所有可能的括号,可以通过删除无效括号来生成,例如

Input : str = “()())()” -
Output : ()()() (())()
There are two possible solutions
"()()()" and "(())()"

Input : str = (v)())()
Output : (v)()() (v())()

在这个问题中,我们将使用回溯法来打印所有有效的序列。

寻找解决方案的方法

在这种方法中,我们将尝试使用广度优先搜索 (BFS) 一一删除左括号和右括号。现在,对于每个序列,我们检查它是否有效。如果有效,则将其打印为输出。

示例

Open Compiler
#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; }

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

Input : (v)())()
Output : (v())()

上述代码的解释

在上述方法中,我们简单地一一删除括号,并且在我们删除括号的同时,我们也跟踪之前的序列,这样我们就不会两次检查同一个序列。如果我们从所有这些可能性中找到一个有效的序列,我们将打印所有有效的可能性,这就是我们的程序的执行过程。

结论

在本教程中,我们解决了一个问题,即查找并删除无效括号。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法(常规方法)。我们可以使用 C、Java、Python 等其他语言编写相同的程序。希望您觉得本教程有所帮助。

更新于:2021年11月26日

180 次浏览

开启您的职业生涯

通过完成课程获得认证

开始
广告