หาจุดเท่ากัน (Equal Point) ในสตริงวงเล็บด้วย C++

ที่นี่เราจะดูวิธีหาจุดเท่ากัน (Equal Point) ในสตริงของวงเล็บ จุดเท่ากันคือดัชนี i ที่ทำให้จำนวนวงเล็บเปิด (Opening Brackets) ก่อนหน้ามันเท่ากับจำนวนวงเล็บปิด (Closing Brackets) หลังจากมัน สมมติสตริงวงเล็บเป็น "(()))(()()())))" ถ้าเราดูอย่างใกล้ชิด เราสามารถได้

ดังนั้น จำนวนวงเล็บเปิดจาก 0 ถึง 9 คือ 5 และจำนวนวงเล็บปิดจาก 9 ถึง 14 ก็คือ 5 ดังนั้นนี่คือจุดเท่ากัน

เพื่อแก้ปัญหานี้ เราต้องทำตามขั้นตอนน้อยๆ ดังนี้ -

• เก็บจำนวนวงเล็บเปิดที่ปรากฏในสตริงจนถึงดัชนี i ทุกดัชนี
• เก็บจำนวนวงเล็บปิดที่ปรากฏในสตริงจนถึงดัชนี i ทุกดัชนี แต่ควรทำจากดัชนีสุดท้าย (Backward)
• ตรวจสอบว่ามีดัชนีไหนที่มีค่าวงเล็บเปิดและวงเล็บปิดเท่ากัน

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

#include <iostream>
#include <cmath>
using namespace std;

int findEqualPoint(string str) {
    int total_length = str.length();
    int open[total_length+1] = {0}, close[total_length+1] = {0};
    int index = -1;
    open[0] = 0;
    close[total_length] = 0;
    if (str[0]=='(') // ตรวจสอบว่าวงเล็บแรกเป็นเปิดหรือไม่ ถ้าใช่ open[1] = 1
        open[1] = 1;
    if (str[total_length-1] == ')') // ตรวจสอบว่าวงเล็บสุดท้ายเป็นปิดหรือไม่ ถ้าใช่
        close[total_length-1] = 1;
    for (int i = 1; i < total_length; i++) {
        if (str[i] == '(')
            open[i+1] = open[i] + 1;
        else
            open[i+1] = open[i];
    }
    for (int i = total_length-2; i >= 0; i--) {
        if (str[i] == ')')
            close[i] = close[i+1] + 1;
        else
            close[i] = close[i+1];
    }
    if (open[total_length] == 0)
        return total_length;
    if (close[0] == 0)
        return 0;
    for (int i = 0; i <= total_length; i++)
        if (open[i] == close[i])
            index = i;
    return index;
}

int main() {
    string str = "(()))(()()())))";
    cout << "Index of equal point: " << findEqualPoint(str);
}

ผลลัพธ์

Index of equal point: 9