C++ alih keluar kurungan tidak sah daripada ungkapan

Memandangkan urutan kurungan sekarang, anda perlu mencetak semua kemungkinan kurungan yang boleh dibuat dengan mengalih keluar kurungan yang tidak sah, contohnya

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

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

Dalam soalan ini, kami akan menggunakan kaedah penjejakan belakang untuk mencetak semua urutan yang sah .

Kaedah Penyelesaian

Dalam kaedah ini, kami akan cuba membuang kurungan terbuka dan tertutup satu persatu menggunakan BFS. Sekarang untuk setiap urutan kami menyemak sama ada ia sah. Jika sah, cetak sebagai output.

Contoh

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

Output

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

Penjelasan kod di atas

Dalam kaedah di atas, kami mengeluarkan kurungan satu demi satu, dan kami juga menjejaki urutan sebelumnya untuk mengelakkan menyemak urutan yang sama berulang kali. Jika kami menemui urutan yang sah, kami mencetak semua kemungkinan yang sah, dan ini adalah bagaimana program kami dilaksanakan.

Kesimpulan

Dalam tutorial ini, kami menyelesaikan masalah mencari dan mengalih keluar kurungan tidak sah. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan penyelesaian lengkap (pendekatan biasa). Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan bahasa lain. Semoga tutorial ini dapat membantu anda.

Atas ialah kandungan terperinci C++ alih keluar kurungan tidak sah daripada ungkapan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!