070. Score of Parentheses

Interview · Download this solution · All solutions and shared helpers

Problem

Given a balanced parentheses string, compute its score: () has score one, concatenation adds scores, and wrapping a nonempty balanced expression doubles its score. Empty input has score zero. Return an integer.

Examples

Example 1

parentheses_score("(()(()))")
=> 6

The outer group doubles the sum one plus two.

Example 2

parentheses_score("()()")
=> 2

Sibling groups add.

Example 3

parentheses_score("")
=> 0

The outer context remains zero.

Reveal the worked solution and reasoning

Why this mechanism works

Each nesting level accumulates the scores of its completed children. When a level closes, an empty child context represents (), worth one; otherwise its accumulated score is doubled. Add that completed group to its parent context.

State and boundaries

stack holds one running score per open context, beginning with an outer zero context.

Protocol

Push a zero score on '('.
On ')' pop the child's accumulated score.
Convert zero to one, otherwise double it.
Add the group score to the parent.
Return the outer score.

Visualization

(()(()))
children: ()=1 and (())=2
inside score=3
outer wrapping -> 6

Python implementation

def parentheses_score(text):
    stack = [0]
    for char in text:
        if char == '(':
            stack.append(0)
        else:
            inside = stack.pop()
            stack[-1] += 1 if inside == 0 else 2 * inside
    return stack[0]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

parentheses_score("(()(()))")

L2 parentheses_score: stack = [0]
text='(()(()))'; stack=[0]

L3 parentheses_score: for char in text:
text='(()(()))'; stack=[0]; char='('

L5 parentheses_score: stack.append(0)
text='(()(()))'; stack=[0, 0]; char='('

L5 parentheses_score: stack.append(0)
text='(()(()))'; stack=[0, 0, 0]; char='('

L3 parentheses_score: for char in text:
text='(()(()))'; stack=[0, 0, 0]; char=')'

L7 parentheses_score: inside = stack.pop()
text='(()(()))'; stack=[0, 0]; char=')'; inside=0

L8 parentheses_score: stack[-1] += 1 if inside == 0 else 2 * inside
text='(()(()))'; stack=[0, 1]; char=')'; inside=0

L3 parentheses_score: for char in text:
text='(()(()))'; stack=[0, 1]; char='('; inside=0

... 5 intermediate state changes omitted ...

L7 parentheses_score: inside = stack.pop()
text='(()(()))'; stack=[0, 1]; char=')'; inside=1

L8 parentheses_score: stack[-1] += 1 if inside == 0 else 2 * inside
text='(()(()))'; stack=[0, 3]; char=')'; inside=1

L7 parentheses_score: inside = stack.pop()
text='(()(()))'; stack=[0]; char=')'; inside=3

L8 parentheses_score: stack[-1] += 1 if inside == 0 else 2 * inside
text='(()(()))'; stack=[6]; char=')'; inside=3

Result: 6. The outer group doubles the sum one plus two.

parentheses_score("()()")

L2 parentheses_score: stack = [0]
text='()()'; stack=[0]

L3 parentheses_score: for char in text:
text='()()'; stack=[0]; char='('

L5 parentheses_score: stack.append(0)
text='()()'; stack=[0, 0]; char='('

L3 parentheses_score: for char in text:
text='()()'; stack=[0, 0]; char=')'

L7 parentheses_score: inside = stack.pop()
text='()()'; stack=[0]; char=')'; inside=0

L8 parentheses_score: stack[-1] += 1 if inside == 0 else 2 * inside
text='()()'; stack=[1]; char=')'; inside=0

L3 parentheses_score: for char in text:
text='()()'; stack=[1]; char='('; inside=0

L5 parentheses_score: stack.append(0)
text='()()'; stack=[1, 0]; char='('; inside=0

L3 parentheses_score: for char in text:
text='()()'; stack=[1, 0]; char=')'; inside=0

L7 parentheses_score: inside = stack.pop()
text='()()'; stack=[1]; char=')'; inside=0

L8 parentheses_score: stack[-1] += 1 if inside == 0 else 2 * inside
text='()()'; stack=[2]; char=')'; inside=0

Result: 2. Sibling groups add.

Why the solution is correct

An open context begins with no completed children, hence score zero. Closing applies exactly the primitive or wrapping rule, and adding to the parent applies concatenation. Structural induction over groups gives the full expression's score.

Time and space

O(n) arithmetic operations and O(d) stack entries; large scores require additional integer bits.

Common mistakes

Always doubling would give () a score of zero. Returning the last child rather than adding it loses sibling groups.

Reasoning card

State: stack holds one running score per open context, beginning with an outer zero context.

Invariant: Stack/depth accurately represents unmatched opening contexts.

Decision to rehearse: Use depth or stack contexts; commit score when a primitive pair closes.

Finish: Return the outer score

Transfer exercise

Derive an alternative that adds 2**depth for each primitive () pair, and prove that it matches the nesting rule.