C++ ลบ Parentheses ที่ไม่ถูกต้องออกจากนิพจน์

กำหนดลำดับ parentheses ตอนนี้ คุณต้องพิมพ์ parentheses ที่เป็นไปได้ทั้งหมดที่มันสามารถสร้างได้โดยการลบ bracket ที่ไม่ถูกต้อง ตัวอย่างเช่น:

Input : str = "()())()" - Output : ()()() (())()
มีสองคำตอบที่เป็นไปได้ "()()()" และ "(())()"

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

ในปัญหานี้ เราจะใช้ backtracking เพื่อที่จะพิมพ์ลำดับที่ถูกต้องทั้งหมด

วิธีการหาคำตอบ

ในวิธีนี้ เราจะพยายามลบ opening และ closing brackets ทีละตัวโดยใช้ BFS ตอนนี้สำหรับแต่ละลำดับ เราตรวจสอบว่ามันถูกต้องหรือไม่ ถ้าถูกต้อง เราจะพิมพ์มันเป็น output ของเรา

ตัวอย่าง

#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; // ถ้าเราตรวจสอบสตริงนั้นแล้ว เราใส่ลงใน visit
                       // เพื่อที่เราจะไม่เจอสตริงนั้นอีก
    queue q; // queue สำหรับทำ BFS
    string temp;
    bool level;
    // push สตริงที่กำหนดเป็นโหนดเริ่มต้นเข้า queue
    q.push(str);
    visit.insert(str);
    while (!q.empty()){
        str = q.front(); q.pop();
        if (validString(str)){
            cout << str << "\n"; // เราพิมพ์สตริงของเรา
            level = true; // เนื่องจากเราพบสตริงในระดับเดียวกัน เราไม่ต้อง apply bfs จากมัน
        }
        if (level)
            continue;
        for (int i = 0; i < str.length(); i++){
            if (!isParenthesis(str[i])) // เราจะไม่ลบตัวอักษรอื่นๆ นอกจาก bracket
                continue;
            temp = str.substr(0, i) + str.substr(i + 1); // ลบ parentheses จากสตริงทีละตัว
            if (visit.find(temp) == visit.end()) { // ถ้าเราตรวจสอบสตริงนั้นแล้ว เราจะไม่ตรวจสอบอีก
                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())()

คำอธิบายโค้ด

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

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาการหา Remove Invalid Parentheses เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ปกติ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์