Score of Parentheses

Overview

Score of parentheses: "()" = 1; "AB" = A + B (concatenation); "(A)" = 2 A (nested). Balanced string only. Use a stack of scores: on '(', push 0 (score for this level); on ')', pop inner score v, pop outer w, push w + max(2v, 1). Final score is stack[0].

When to Use

• Nested scoring with brackets — score depends on depth or nesting.
• Expression with ( ) — similar stack of values per level.
• Count balanced substrings — stack of indices or scores.

How It Works

Stack = running score at each nesting level. '(' opens a new level (push 0). ')' closes: inner score v becomes 1 if v was 0, else 2*v; add that to the parent (new top) and push back.

Example 1: Stack of Scores (Standard)

function scoreOfParentheses(s: string): number {
  const stack: number[] = [0];
  for (const c of s) {
    if (c === '(') stack.push(0);
    else {
      const v = stack.pop()!;
      const w = stack.pop()!;
      stack.push(w + Math.max(2 * v, 1));
    }
  }
  return stack[0];
}

Time: O(n). Space: O(n).

Example 2: Depth / Count Approach

Each pair "()" at depth d contributes 2^d. Track depth: on '(', depth++; on ')', if previous was '(', add 2^(depth-1), then depth--.

function scoreOfParenthesesDepth(s: string): number {
  let score = 0, depth = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') depth++;
    else {
      depth--;
      if (s[i - 1] === '(') score += 1 << depth;
    }
  }
  return score;
}

Example 3: Step-by-Step Trace

s = "(()(()))". Stack start [0]. '(': [0,0]. '(': [0,0,0]. ')': v=0,w=0 → push 0+1 → [0,1]. '(': [0,1,0]. '(': [0,1,0,0]. ')': [0,1,1]. ')': v=1,w=1 → 1+2 → [0,3]. ')': v=3,w=0 → 0+6 → [6]. Return 6.

Example 4: Edge Cases

• "()" — push 0, then pop 0,0 → push 1; return 1.
• "()()" — [0]→[0,0]→[1]→[1,0]→[2]; return 2.
• "(())" — [0,0,0]→[0,1]→[2]; return 2.
• Empty — assume valid non-empty or return 0.

Example 5: Variant — Sum of Depths

If score were "sum of depths of each '()'": on '(' depth++; on ')' add depth, then depth--. Same single-pass idea, different formula.

Summary

• Score of parentheses: stack of per-level scores; on ')' pop inner v and outer w, push w + max(2*v,1). Alternative: 2^depth at each "()". See Valid Parentheses, Stack Basics.