Score of Parentheses

Problem

Given a balanced parentheses string, compute its score by these three rules: - () (an empty pair) scores 1. - AB (two balanced strings side by side) scores A + B — add the pieces. - (A) (a balanced string wrapped in one pair) scores 2 * A — double the inside. A "balanced" string is one where every ( has a matching ) and they nest correctly. Return the total score.

Constraints

• 2 ≤ s.length ≤ 50
• s contains only ( and ) and is guaranteed balanced
• Every score is a positive integer (the rules never produce 0 or negatives)

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def scoreOfParentheses(self, s):
        stack = [0]
        for c in s:
            if c == '(':
                stack.append(0)
            else:
                v = stack.pop()
                stack[-1] += max(2 * v, 1)
        return stack[0]

Java

import java.util.Stack;

class Solution {
    public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0); // The score of the current frame

        for (char c: S.toCharArray()) {
            if (c == '(')
                stack.push(0);
            else {
                int v = stack.pop();
                int w = stack.pop();
                stack.push(w + Math.max(2 * v, 1));
            }
        }

        return stack.pop();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.