856. Score of Parentheses

T: O(n)
S: O(n)

```java
class Solution {
    /*
    (()(()))
           x
    6
    */
    public int scoreOfParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                    stack.push('1'); // () case
                } else {
                    int sum = 0;
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sum += (stack.pop() - '0'); // ()()(()()) case
                    }
                    stack.pop();
                    stack.push((char)(2*sum + '0')); // ( 3 ) case, so 2*3
                }
            }
        }
        int result = 0;
        while (!stack.isEmpty()) {
            result += (stack.pop() - '0');
        }
        return result;
    }
}

/*
T: O(n)
S: O(n)
*/
```