C++ में एक एक्सप्रेशन से अवैध पैरेंथेसिस को हटाना

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

इनपुट: str = "()())()"
आउटपुट: ()()() (())()
दो संभावित समाधान हैं "()()()" और "(())()"

इनपुट: str = "(v)())()"
आउटपुट: (v)()() (v())()

इस समस्या में, हम बैकट्रैकिंग का उपयोग करने जा रहे हैं ताकि यह सभी वैध अनुक्रमों को प्रिंट करे।

समाधान खोजने का दृष्टिकोण

इस दृष्टिकोण में, हम BFS का उपयोग करके ओपनिंग और क्लोजिंग ब्रैकेट को एक-एक करके हटाने का प्रयास करेंगे। अब प्रत्येक अनुक्रम के लिए, हम जांचते हैं कि क्या यह वैध है या नहीं। यदि यह वैध है, तो हम इसे अपने आउटपुट के रूप में प्रिंट करते हैं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

bool isParenthesis(char c) {
    return ((c == '(') || (c == ')'));
}

bool validString(string 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;
    }
    return (cnt == 0);
}

void validParenthesesSequences(string str) {
    if (str.empty())
        return;
    set visit; // यदि हमने उस स्ट्रिंग की जांच की तो हम इसे विजिट में डालते हैं
    // ताकि हम उस स्ट्रिंग का फिर से सामना न करें
    queue q; // BFS करने के लिए क्यू
    string temp;
    bool level;
    // दी गई स्ट्रिंग को शुरुआती नोड के रूप में क्यू में पुश करना
    q.push(str);
    visit.insert(str);
    while (!q.empty()) {
        str = q.front(); q.pop();
        if (validString(str)) {
            cout << str << "\n"; // हम अपनी स्ट्रिंग प्रिंट करते हैं
            level = true; // चूंकि हमने उसी लेवल पर स्ट्रिंग ढूंढी इसलिए हमें इससे BFS लागू करने की आवश्यकता नहीं है
        }
        if (level)
            continue;
        for (int i = 0; i < str.length(); i++) {
            if (!isParenthesis(str[i])) // हम अपनी स्ट्रिंग से ब्रैकेट के अलावा किसी अन्य वर्ण को नहीं हटाएंगे
                continue;
            temp = str.substr(0, i) + str.substr(i + 1); // स्ट्रिंग्स से पैरेंथेसिस को एक-एक करके हटाना
            if (visit.find(temp) == visit.end()) { // यदि हम उस स्ट्रिंग की जांच करते हैं तो हम इसे फिर से जांच नहीं करेंगे
                q.push(temp);
                visit.insert(temp);
            }
        }
    }
}

int main() {
    string s1;
    s1 = "(v)())()";
    cout << "इनपुट: " << s1 << "\n";
    cout << "आउटपुट: ";
    validParenthesesSequences(s1);
    return 0;
}

आउटपुट

इनपुट: (v)())()
आउटपुट: (v())()

उपरोक्त कोड की व्याख्या

उपरोक्त दृष्टिकोण में, हम केवल एक-एक करके अपने पैरेंथेसिस को हटाते हैं। अब चूंकि हम ब्रैकेट को हटा सकते हैं, हम पिछले अनुक्रमों का ट्रैक भी रखते हैं ताकि हम उसी अनुक्रम को दो बार जांच न करें। अब यदि हमें इन सभी संभावनाओं में से कोई वैध अनुक्रम मिलता है, तो हम सभी वैध संभावनाओं को प्रिंट करते हैं और इस तरह हमारा प्रोग्राम आगे बढ़ता है।

निष्कर्ष

इस ट्यूटोरियल में, हम अवैध पैरेंथेसिस को हटाने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।