Score of Parentheses
Medium · stack
You are given a balanced string s made only of the characters ( and ). Its score follows three rules:
()scores1.- Two balanced strings written one after the other score the sum of their scores.
- A balanced string wrapped in a pair of brackets,
(A), scores twice the score ofA.
Return the score of s. The score can be huge, so return it modulo 10^9 + 7.
Examples
Example 1
Input: s = "(()(()))"
Output: 6
Inside the outer brackets are () which scores 1 and (()) which scores 2, so the inside scores 3 and the whole string scores 6.
Example 2
Input: s = "()(())"
Output: 3
() scores 1 and (()) scores 2, side by side they add up to 3.
Example 3
Input: s = "((()))"
Output: 4
The innermost () scores 1 and each of the two wrapping brackets doubles it.
Constraints
- 2 <= len(s) <= 10^4
- s contains only the characters ( and )
- s is balanced: every ( has a matching ) after it