Điểm số chuỗi ngoặc đơn C++ (Score of Parentheses)

Cho chuỗi ngoặc đơn cân bằng S, tính điểm theo quy tắc: 1. "()" = 1 điểm 2. AB = A + B (nối chuỗi) 3. (A) = 2 × A (bao quanh)

Ví dụ

Input - "(()(()))" Output - 6

Giải thích - ( () (()) ) = 2 × (1 + 2×1) = 2 × 3 = 6.

Phương pháp tiếp cận (Stack)

• Duyệt chuỗi, push -1 cho '('
• Gặp ')':
  • Nếu top = -1: pop, push 1 (cặp "()")
  • Ngược: pop cộng dồn cho đến -1, nhân 2, push kết quả
• Cuối cùng cộng tất cả giá trị trong stack

Ví dụ code C++

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

class Solution {
public:
    int scoreOfParentheses(string S) {
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < S.size(); i++) {
            if (S[i] == '(') {
                st.push(-1);
            } else {
                if (st.top() == -1) {
                    st.pop();
                    st.push(1);
                } else {
                    int x = 0;
                    while (st.top() != -1) {
                        x += st.top();
                        st.pop();
                    }
                    x *= 2;
                    st.pop();
                    st.push(x);
                }
            }
        }
        while (!st.empty()) {
            ans += st.top();
            st.pop();
        }
        return ans;
    }
};

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

Kết quả

6