856. Score of Parentheses

這題是一個典型的stack, 不是特別好想

我們可以看到我們會有幾種狀況,

首先, 當我們看到 ( 的時候, 當前有幾種狀況

第一個, 已經有值了

例如

()(

等於是目前的值已經是1, 接著又遇到左括號,

那這個怎麼辦, 我們就先把1推到stack裡, 並且讓值先改回零, 我們只需重新去看後面新的左括號的結果

我們先說左括號的兩種做法, 等等再來看右括號怎麼處理

(

一樣也是會推0到stack

所以左括號不管遇到什麼情況, 都是直接將值推入stack中, 並且將值歸零

而當遇到右括號, 會有兩種狀況

假設是

()(")"

當回來的那一瞬間, 我們先去看當前有沒有值, 沒有值, 代表, 左右括號中間根本沒有人, 而他們就形成一個1

所以處理的方式就是, 目前的值變成1之外, 你還要將原本已經推進去的那個加回來

cur = 1+ st.top()

而如果是有值, 代表中間其實還有其他括號, 這時就是乘2, 並且一樣把原本去掉的人給吐回來

cur = cur * 2 + st.top()

這樣一來, 就可以在O(n)時間內完成

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