सी ++ एक अभिव्यक्ति से अमान्य कोष्ठक निकालें

एक कोष्ठक अनुक्रम को देखते हुए; अब, आपको उन सभी संभावित कोष्ठकों को प्रिंट करना होगा, जिन्हें वह अमान्य कोष्ठकों को हटाकर बना सकता है, उदाहरण के लिए

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++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।