> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/stack-and-queue/856.-score-of-parentheses.md).

# 856. Score of Parentheses

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

````java
```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)
*/
```
````