พิมพ์หมายเลขวงเล็บ (Bracket Number) ใน C++

โจทย์

ให้นิพจน์ที่มีวงเล็บ ต้องการพิมพ์หมายเลขลำดับของวงเล็บ ตัวอย่าง: ((()())()) → 1 2 3 3 4 4 2 5 5 1

วิธีแก้ปัญหา (Stack)

1. ตัวนับ leftBracket เริ่มที่ 1
2. Stack เก็บหมายเลขวงเล็บซ้าย
3. เจอ '(' → พิมพ์ leftBracket, push เข้า stack, leftBracket++
4. เจอ ')' → พิมพ์ top ของ stack, pop

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

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

void bracketCount(string expression, int n) {
    int leftBracket = 1;
    stack<int> rightBracket;
    for (int i = 0; i < n; i++) {
        if (expression[i] == '(') {
            cout << leftBracket << " ";
            rightBracket.push(leftBracket);
            leftBracket++;
        } else if (expression[i] == ')') {
            cout << rightBracket.top() << " ";
            rightBracket.pop();
        }
    }
}

int main() {
    string expression = "()((())()())";
    int n = expression.size();
    bracketCount(expression, n);
    return 0;
}

ผลลัพธ์

1 1 2 3 4 4 3 5 5 6 6 2