# 0856. Score of Parentheses
###### tags: `Leetcode` `Medium` `Stack` `Parentheses`
Link: https://leetcode.com/problems/score-of-parentheses/
## 思路
### 思路一 $O(N)$ $O(1)$
只看最里面的()是第几层的
### 思路二 Stack $O(N)$ $O(N)$
参考[这里](https://leetcode.com/problems/score-of-parentheses/discuss/1856519/JavaC%2B%2B-Visually-Explained!!)
也可以看注释理解

## Code
### 思路一 $O(N)$ $O(1)$

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ans = 0
        bal = 0
        for i, c in enumerate(s):
            if c == '(':
                bal += 1
            else:
                bal -= 1
                if s[i-1] == '(': ans += 1<<bal
        return ans

class Solution {
    public int scoreOfParentheses(String s) {
        int ans=0, bal=0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='(') bal++;
            else{
                bal--;
                if(s.charAt(i-1)=='(') ans+=1<<bal;
            }
        }
        return ans;
    }
}

### 思路二 Stack $O(N)$ $O(N)$

class Solution {
    public int scoreOfParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='(') stack.add(0);
            else{
                int v = stack.pop(); //current score of 当下()里面包着的东西
                int w = stack.pop(); //current score of 与当下()并排的上一个()
                w += Math.max(2*v, 1);
                stack.add(w);
            }
        }
        return stack.peek();
    }
}