คะแนนของวงเล็บ (Score of Parentheses) ใน C++

ได้รับสตริงวงเล็บที่สมดุล (balanced parentheses) งานคือคำนวณคะแนนตามกติกา:

• () = 1 คะแนน
• AB = A + B (ต่อกัน)
• (A) = 2 × A

ตัวอย่าง

Input − "(()(()))" Output − 6

คำอธิบาย − ( () (()) ) = 2 × (1 + 2×1) = 2 × 3 = 6

แนวทางการแก้ปัญหา (Stack)

• ใช้ stack เก็บค่า: -1 แทน '(', คะแนนสำหรับ ')'
• เจอ '(' → push -1
• เจอ ')': ถ้าบนสุดเป็น -1 → pop แล้ว push 1 (ค่า () = 1)
• ถ้าบนสุดไม่ใช่ -1 → รวมค่าจนเจอ -1, คูณ 2, push กลับ
• สุดท้ายรวมค่าใน stack ทั้งหมด

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

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

class Solution {
public:
    int scoreOfParentheses(string S) {
        stack st;
        for (char c : S) {
            if (c == '(') st.push(-1);
            else {
                if (st.top() == -1) {
                    st.pop(); st.push(1);
                } else {
                    int sum = 0;
                    while (st.top() != -1) {
                        sum += st.top(); st.pop();
                    }
                    st.pop(); // remove -1
                    st.push(sum * 2);
                }
            }
        }
        int ans = 0;
        while (!st.empty()) { ans += st.top(); st.pop(); }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.scoreOfParentheses("(()(()))"); // 6
    return 0;
}

ผลลัพธ์

6