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())()

คำอธิบายของโค้ดด้านบน

ในแนวทางข้างต้น เราเอาวงเล็บออกทีละตัวในขณะที่เราทำวงเล็บเหลี่ยมได้ เรายังติดตามลำดับก่อนหน้าด้วย เพื่อที่เราจะไม่ตรวจสอบลำดับเดิมซ้ำ 2 ครั้งในตอนนี้ หากเราพบลำดับที่ถูกต้องจากความเป็นไปได้ทั้งหมดเหล่านี้ เราพิมพ์ความเป็นไปได้ที่ถูกต้องทั้งหมด และนั่นคือวิธีที่โปรแกรมของเราดำเนินการ

บทสรุป

ในบทช่วยสอนนี้ เราจะแก้ปัญหาเพื่อค้นหา Remove Invalid Parenthes นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์