# 856     Score of Parentheses

## 856. [Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/description/)

## 1. Question

Given a balanced parentheses string`S`, compute the score of the string based on the following rule:

* `()`has score 1
* `AB`has score`A + B`, where A and B are balanced parentheses strings.
* `(A)`has score`2 * A`, where A is a balanced parentheses string.

**Example 1:**

```
Input: "()"
Output: 1
```

**Example 2:**

```
Input: "(())"
Output: 2
```

**Example 3:**

```
Input: "()()"
Output: 2
```

**Example 4:**

```
Input: "(()(()))"
Output: 6
```

**Note:**

1. `S`is a balanced parentheses string, containing only`(`and`)`.
2. `2 <= S.length <= 50`

## 2. Implementation

**(1) Stack**

```java
class Solution {
    public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack();

        for (char c : S.toCharArray()) {
            if (c == '(') {
                stack.push(-1);
            }
            else {
                int score = 0;
                while (stack.peek() != -1) {
                    score += stack.pop();
                }
                stack.pop();
                // score不等于0时，说明有嵌套的括号出现，分数加倍
                stack.push(score == 0 ? 1 : 2 * score);
            }
        }

        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

**Stack**: 时间复杂度: O(n), 空间复杂度: O(n)
