> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/stacks-and-queues/score-of-parentheses.md).

# Score of Parentheses

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`

```java
class Solution {
    public int scoreOfParentheses(String S) {
        S = '(' + S + ')';
        Deque<String> st = new LinkedList<>();
        for (char c : S.toCharArray()) {
            if (c == ')') {
                int sum = 0;
                while (!st.peek().equals("("))
                    sum += Integer.parseInt(st.pop());
                st.pop();
                st.push(sum == 0 ? "1" : Integer.toString(sum * 2));
            } else
                st.push(c + "");
        }
        return Integer.parseInt(st.pop()) / 2;
    }
}
```