Given a parentheses sequence; now, you have to print all the possible parentheses that it can make by removing the invalid brackets, for example
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和其他語言來寫相同的程式。希望本教學對您有所幫助。
以上是C++ 從表達式中刪除無效的括號的詳細內容。更多資訊請關注PHP中文網其他相關文章！
