นับคู่ของลำดับวงเล็บที่สมดุลใน C++

เราได้รับสตริงที่มีวงเล็บ และงานคือคำนวณจำนวนคู่ของลำดับวงเล็บที่สามารถสร้างได้โดยที่วงเล็บเป็นสมดุล

วงเล็บถูกเรียกว่าสมดุลเมื่อมีจำนวนวงเล็บเปิดและปิดเท่ากัน วงเล็บที่ใช้ไปแล้วไม่สามารถนำมาใช้ซ้ำสำหรับสร้างคู่ได้

อินพุต − string paran[] = { ")()())", "(", ")(", ")(", ")" }

เอาต์พุต − จำนวนคู่ของลำดับวงเล็บที่สมดุล คือ 1

คำอธิบาย − เราจะนำทุกชุดของสตริงมาคำนวณจำนวน มาเลือกอิลิเมนต์แรกเป็น ")()())" ซึ่งมีวงเล็บปิด 4 ตัวและวงเล็บเปิด 2 ตัว เราจะมองหาอิลิเมนต์ถัดไปที่มีวงเล็บปิด 2 ตัวพอดีเพื่อทำให้สมดุล ซึ่งไม่มีในสตริง จึงทิ้งไปพิจารณาต่อ คู่ที่ถูกต้องที่มีวงเล็บเปิดและปิดเท่ากันอยู่ที่ (2, 5) ดังนั้นจำนวนคือ 1

อินพุต − string paran[] = { ")()())", "((", "(", ")(", ")(", ")" }

เอาต์พุต − จำนวนคู่ของลำดับวงเล็บที่สมดุล คือ 2

คำอธิบาย − คู่วงเล็บที่สมดุลอยู่ที่ (1, 2) และ (3, 6) ดังนั้นจำนวนคือ 2

แนวทางที่ใช้ในโปรแกรม

• รับสตริงและคำนวณความยาวสตริงด้วยฟังก์ชัน length() ส่งข้อมูลไปฟังก์ชันเพื่อประมวลผลต่อ
• ใช้ตัวแปรชั่วคราว count เก็บคู่ที่ถูกต้อง และสร้าง um_1 และ um_2 เป็น unordered_map
• เริ่มลูป FOR จาก 0 ถึงขนาดของสตริง
• ในลูป กำหนด str เป็น paran[i] คำนวณความยาวอีกครั้ง
• ตัวแปรชั่วคราว first และ last เริ่มต้นเป็น 0
• ลูป FOR อีกชั้นจาก j=0 ถึงความยาวสตริง
• ในลูป ตรวจสอบถ้า str[j] == '(' เพิ่ม first 1 มิฉะนั้นถ้า first == 1 ลด first 1 มิฉะนั้นเพิ่ม last 1
• ตรวจสอบถ้า first == 1 && last != 1 ทำ um_1[first]++ ถ้า last == 1 && first != 1 ทำ um_2[last]++ และถ้า first != 1 && last != 1 เพิ่ม count 1
• กำหนด count = count / 2
• ลูปจาก 0 ถึง um_1 กำหนด count เป็นค่าต่ำสุดจาก um_1.second และ um_2.first
• คืนค่า count
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด C++

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

int parentheses(string paran[], int size){
    int count = 0;
    unordered_map<int, int> um_1, um_2;
    for (int i = 0; i < size; i++){
        string str = paran[i];
        int len = str.length();
        int first = 0;
        int last = 0;
        for (int j = 0; j < len; j++){
            if (str[j] == '('){
                first++;
            } else {
                if (first==1){
                    first--;
                } else {
                    last++;
                }
            }
        }
        if(first==1 && last!=1){
            um_1[first]++;
        }
        if (last==1 && first!=1){
            um_2[last]++;
        }
        if(first!=1 && last!=1){
            count++;
        }
    }
    count = count / 2;
    for (auto it : um_1){
        count += min(it.second, um_2[it.first]);
    }
    return count;
}

int main(){
    string paran[] = { ")()())", "(", ")(", ")(", ")" };
    int size = sizeof(paran) / sizeof(paran[0]);
    cout<<"Count of pairs of parentheses sequences such that parentheses are balanced are: "<<parentheses(paran, size);
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of pairs of parentheses sequences such that parentheses are balanced are: 1