856. Score of Parentheses

stack一直是我的罩門, 我今天特別花時間研究一翻

我想要把整個過程記錄下來, 好幫助我記憶

首先我們有一個stack, 跟目前狀態 cur = 0
(()(()))
step1: (
stack:塞入cur: 目前只有0 [0]
step2: (
stack在塞入cur: st: [0, 0]
step3: )
因為一個對稱的括號完成, 先將cur * 2, 發現cur == 0, 代表這只有"()", 所以改成cur = 1, 並且把最上層的數值取出, 加到 cur, cur = max(cur *2, 1) + 0, cur = 1
stack狀態: [0]
step4: (
又是一個開括號, 將cur 存入stack, cur 設為0,
stack: [0, 1]
step5: (
同step2
stack: [0, 1, 0]
step6: )
因為一個對稱的括號完成, 先將cur * 2, 發現cur == 0, 代表這只有"()", 所以改成cur = 1, 並且把最上層的數值取出, 加到 cur, cur = max(cur *2, 1) + 0, cur = 1
stack: [0, 1]
step7: )
因為一個對稱的括號完成, 先將cur * 2, cur = 1, 並且把最上層的數值取出, 加到 cur, cur = max(cur *2, 1) + 1, cur = 3
stack: [0]
step8: )
因為一個對稱的括號完成, 先將cur * 2, cur = 1, 並且把最上層的數值取出, 加到 cur, cur = max(cur *2, 1) + 0, cur = 6

挖 這真的沒有特別想還是很難想通, 看來我要對stack進行一番集訓

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st;
        int cur = 0;
        for(auto c: s){
            if(c == '('){
                st.push(cur);
                cur = 0;
            }else{
                cur = max(cur * 2, 1) + st.top();
                st.pop();
            }
        }
        return cur;
    }
};