C++ supprime les crochets non valides de l'expression

Étant donné une séquence de parenthèses maintenant, vous devez imprimer toutes les parenthèses possibles qu'elle peut faire en supprimant les parenthèses invalides, par exemple

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

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

Dans cette question, nous utiliserons la méthode de retour en arrière pour imprimer toutes les séquences valides .

Méthode de solution

Dans cette méthode, nous essaierons de supprimer les crochets ouverts et fermés un par un à l'aide de BFS. Maintenant, pour chaque séquence, nous vérifions si elle est valide. S'il est valide, imprimez-le en sortie.

Exemple

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

Sortie

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

Explication du code ci-dessus

Dans la méthode ci-dessus, nous supprimons les crochets un par un, et nous gardons également une trace de la séquence précédente pour éviter de vérifier la même séquence à plusieurs reprises. Si nous trouvons une séquence valide, nous imprimons toutes les possibilités valides, et c'est ainsi que notre programme s'exécute.

Conclusion

Dans ce tutoriel, nous avons résolu un problème de recherche et de suppression des parenthèses invalides. Nous avons également appris un programme C++ pour résoudre ce problème et une solution complète (approche normale). Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et d'autres langages. J'espère que ce tutoriel vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!