Basic Calculator

Every stack in this section so far has held items waiting for something: an opener waiting for its closer, a number waiting for an operator, a day waiting for a warmer day. This problem uses the stack differently. It holds suspended context — "where I was" before entering a parenthesis — the same way a program's call stack saves a function's local variables when it calls another function.

It is a common hard problem at large companies, and it rewards careful, calm code more than cleverness.

The problem

You are given a string holding a valid expression made of non-negative integers, +, -, parentheses and spaces. A - may also be unary, as in -(2 + 3) or -5 at the start. Evaluate it without using a built-in expression evaluator.

• "12 - (4 + 5) + (8 - (1 + 2))" → 8. That is 12 - 9 + 5.
• "-(3 - 5) + 1" → 3. The group is -2, negated to 2, plus 1.

Constraints: 1 ≤ len(s) ≤ 3 × 10⁵; the expression is valid; there are no two operators in a row; every intermediate value fits in 32 bits.

Clarifying questions

• Are * and / possible? No. (That is Basic Calculator II; see the follow-ups.)
• Can a number have several digits? Yes, like 12 or 300.
• Where can unary minus appear? At the start, or right after (. + is never unary.
• Can I use eval? No. That is the point.

Approach 1: the simple way

Repeatedly find the innermost parenthesis group — the first ) and the last ( before it — evaluate its flat contents, and paste the result back in place. When no parentheses are left, evaluate the flat expression.

1def eval_flat(expr: str) -> int:2    """Evaluate digits, + and - with no parentheses. Runs of signs like 1--2 multiply."""3    total, number, sign = 0, 0, 14    reading = False                              # are we in the middle of a number?5    for ch in expr:6        if ch.isdigit():7            number = number * 10 + int(ch)8            reading = True9        else:                                    # a + or -10            if reading:                          # settle the number just finished11                total += sign * number12                number, sign, reading = 0, 1, False13            if ch == "-":14                sign = -sign15    return total + sign * number161718def calculate_by_rewriting(s: str) -> int:19    """Evaluate the innermost ( ... ) and paste its value back, repeat: O(n^2)."""20    s = s.replace(" ", "")21    while "(" in s:22        close = s.index(")")                     # first ) closes the innermost group23        open_ = s.rindex("(", 0, close)24        value = eval_flat(s[open_ + 1:close])25        s = s[:open_] + str(value) + s[close + 1:]26    return eval_flat(s)

Pasting a negative result can create two signs in a row, as in 1-(-2) becoming 1--2, so the flat evaluator multiplies runs of signs together.

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

Each rewrite rebuilds the whole string, and there can be up to n / 2 groups. At 3 × 10⁵ characters, deeply nested, that is tens of billions of character copies. The waste: after evaluating a group, the code forgets where it was and searches the whole string again.

The key insight

Without parentheses, the problem is easy: keep a running result, the sign of the next number, and the number being read. When a + or - arrives, add sign × number to result and set the new sign.

A ( interrupts that. The outer expression is suspended halfway: it has a result so far and a sign waiting to apply to whatever the group turns out to be. So push result and sign onto the stack, and start a fresh sum inside the group with result = 0, sign = 1.

A ) finishes the inner sum. Settle the last number inside it; then pop the sign that was waiting in front of the group and multiply; then pop the outer result and add it back. The outer computation continues as if the whole group were one number.

Nested groups just push deeper. The stack's size is the current nesting depth, and each level remembers exactly what it needs to resume. This is the same thing a call stack does for recursive functions, which is why a recursive-descent parser is the other common solution.

The diagram contrasts this with Next Greater Element II. There, the stack held items waiting for an answer, and the input was extended with a second lap. Here the input is read once, and the stack holds the state of computations that were paused.

Approach 2: one pass, saving context at each parenthesis

1def calculate(s: str) -> int:2    """Evaluate digits, +, -, spaces and parentheses (minus may be unary)."""3    stack: list[int] = []                        # saved (result, sign) pairs, flattened4    result, number, sign = 0, 0, 15    for ch in s:6        if ch.isdigit():7            number = number * 10 + int(ch)       # build multi-digit numbers8        elif ch in "+-":9            result += sign * number              # settle the number just finished10            number = 011            sign = 1 if ch == "+" else -112        elif ch == "(":13            stack.append(result)                 # save the outer context...14            stack.append(sign)15            result, sign = 0, 1                  # ...and start a fresh sum inside16        elif ch == ")":17            result += sign * number18            number = 019            result *= stack.pop()                # the sign written before "("20            result += stack.pop()                # the sum before "("21    return result + sign * number

Spaces match none of the branches, so they are skipped. Unary minus needs no special case: at the start, - settles a number of 0 and sets sign = -1, which then applies to what follows.

Dry run on "12 - (4 + 5) + (8 - (1 + 2))", one row per operator or parenthesis (digits only build number):

The first ) turns the group (4 + 5) into 12 + (-1) × 9 = 3. The innermost (1 + 2) becomes 8 - 3 = 5, and the outer group becomes 3 + 5 = 8.

Time: O(n) — each character is handled once, and each ( pushes two values that one ) pops. Space: O(depth), up to O(n) for deep nesting. Checked against calculate_by_rewriting and Python's eval on 500 random expressions with nested groups and unary minus.

Edge cases

• Unary minus at the start: "-(3 - 5) + 1" saves 0, -1 at the (; the group is -2; -2 × -1 + 0 = 2; then + 1 gives 3.
• Unary minus after (: "1 - (-2)": inside the group, - settles 0 and sets sign = -1, so the group is -2, and the outer - makes it 1 + 2 = 3.
• Number at the very end: it is never followed by an operator, so the final result + sign * number settles it.
• Multi-digit numbers: number * 10 + int(ch) builds 1, then 12, then 123.
• Spaces anywhere: ignored by falling through every branch.

Follow-ups

• "Add * and /, no parentheses" (Basic Calculator II). Keep a stack of signed terms. On + or -, push the number (or its negative). On * or /, pop the last term, combine it with the number, and push the result. The answer is the sum of the stack. Precedence falls out because multiplication binds to the term already on top.
• "All four operators and parentheses" (Basic Calculator III). Use recursion: on (, evaluate the inner expression recursively with the Calculator II logic and treat its value as a number. Or use two stacks, numbers and operators, as in the shunting-yard algorithm.
• "Return the postfix form." Shunting-yard again, then the Reverse Polish Notation lesson evaluates it.