C++ entfernt ungültige Klammern aus dem Ausdruck

Bei einer gegebenen Klammersequenz müssen Sie nun alle möglichen Klammern ausdrucken, die durch Entfernen der ungültigen Klammern entstehen können.

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

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

In dieser Frage verwenden wir die Backtracking-Methode, um alle gültigen Sequenzen auszudrucken .

Lösungsmethode

Bei dieser Methode werden wir versuchen, offene und geschlossene Klammern nacheinander mit BFS zu entfernen. Nun prüfen wir für jede Sequenz, ob sie gültig ist. Wenn gültig, drucken Sie es als Ausgabe aus.

Beispiel

 
#include <bits/stdc++.h>
using namespace std;
bool isParenthesis(char c){
    return ((c == &#39;(&#39;) || (c == &#39;)&#39;));
}
bool validString(string str){
    // cout << str << " ";
    int cnt = 0;
    for (int i = 0; i < str.length(); i++){
        if (str[i] == &#39;(&#39;)
           cnt++;
        else if (str[i] == &#39;)&#39;)
           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&#39;t need to apply bfs from it
        }
        if (level)
            continue;
        for (int i = 0; i < str.length(); i++){
            if (!isParenthesis(str[i])) // we won&#39;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&#39;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;
}

Ausgabe

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

Erläuterung des obigen Codes

In der obigen Methode entfernen wir die Klammern einzeln und behalten außerdem den Überblick über die vorherige Sequenz, um zu vermeiden, dass dieselbe Sequenz wiederholt überprüft wird. Wenn wir eine gültige Sequenz finden, geben wir alle gültigen Möglichkeiten aus und so wird unser Programm ausgeführt.

Fazit

In diesem Tutorial haben wir das Problem gelöst, ungültige Klammern zu finden und zu entfernen. Wir haben auch ein C++-Programm zur Lösung dieses Problems und eine vollständige Lösung gelernt (normaler Ansatz). Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Ich hoffe, dieses Tutorial ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonC++ entfernt ungültige Klammern aus dem Ausdruck. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!