C ++ Xóa dấu ngoặc đơn không hợp lệ khỏi biểu thức

Cho một dãy dấu ngoặc đơn; bây giờ, bạn phải in tất cả các dấu ngoặc đơn mà nó có thể tạo ra bằng cách loại bỏ các dấu ngoặc không hợp lệ, ví dụ

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

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

Trong vấn đề này, chúng tôi sẽ sử dụng backtracking để nó sẽ in tất cả các chuỗi hợp lệ.

Phương pháp tiếp cận để tìm giải pháp

Trong cách tiếp cận này, chúng tôi sẽ cố gắng loại bỏ lần lượt các dấu ngoặc mở và đóng bằng BFS. Bây giờ đối với mỗi trình tự, chúng tôi kiểm tra xem nó có hợp lệ hay không. Nếu nó hợp lệ, chúng tôi sẽ in nó làm đầu ra của chúng tôi.

Ví dụ

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

Đầu ra

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

Giải thích về Quy tắc trên

Trong cách tiếp cận trên, chúng tôi chỉ cần xóa từng dấu ngoặc đơn ngay bây giờ vì chúng tôi có thể mở ngoặc, chúng tôi cũng theo dõi các trình tự trước đó để chúng tôi sẽ không kiểm tra cùng một trình tự hai lần bây giờ nếu chúng tôi tìm thấy một trình tự hợp lệ trong số tất cả các khả năng này , chúng tôi in tất cả các khả năng hợp lệ và đó là cách chương trình của chúng tôi tiến hành.

Kết luận

Trong hướng dẫn này, chúng tôi giải quyết vấn đề để tìm Xóa dấu ngoặc đơn không hợp lệ. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.