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

# 18. 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
```

## Solution: (Stack)

```cpp
class Solution
{
public:
    int scoreOfParentheses(string s)
    {

        stack<int> st;
        st.push(0);

        for (int i = 0; i < s.length(); i++)
        {

            if (s[i] == '(')
            {
                st.push(0);
            }
            else
            {
                int v = st.top();
                st.pop();
                int c = st.top();
                st.pop();
                c += max(1, 2 * v);
                st.push(c);
            }
        }

        return st.top();
    }
};
```

**Time Complexity: O(n)**