C++ একটি অভিব্যক্তি থেকে অবৈধ বন্ধনী সরান

একটি বন্ধনী ক্রম দেওয়া; এখন, আপনাকে সমস্ত সম্ভাব্য বন্ধনী প্রিন্ট করতে হবে যা এটি অবৈধ বন্ধনীগুলি সরিয়ে দিয়ে তৈরি করতে পারে, উদাহরণস্বরূপ

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++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷