Basic Calculator: Stack-Based Expression Evaluation

Basic Calculator is LeetCode 224, rated Hard. You are given a string s representing a mathematical expression containing digits, +, -, parentheses ( and ), and spaces. Your job is to evaluate it and return the result. There is no multiply or divide here, just addition, subtraction, and parentheses for grouping. The difficulty comes entirely from handling nested parentheses correctly, and that is where a stack shines.

The approach: save and restore with a stack

The key insight is that parentheses create nested scopes. When you enter a parenthesized subexpression, you need to evaluate it independently and then fold the result back into the outer expression. A stack lets you "pause" the outer computation, evaluate the inner one, and then "resume" where you left off.

You maintain three variables as you scan through the string:

• result: the running total for the current scope
• sign: either +1 or -1, representing whether the next number gets added or subtracted
• stack: stores pairs of (sign, result) whenever you enter a parenthesized group

When you see an opening parenthesis, push the current result and the current sign onto the stack, then reset both. When you see a closing parenthesis, pop the saved sign and result, and combine them with the value you just finished computing inside the parentheses. Numbers can be multi-digit, so you accumulate digits until you hit a non-digit character.

The solution

def calculate(s: str) -> int:
    result = 0
    sign = 1
    num = 0
    stack = []

    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == '+':
            result += sign * num
            num = 0
            sign = 1
        elif ch == '-':
            result += sign * num
            num = 0
            sign = -1
        elif ch == '(':
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif ch == ')':
            result += sign * num
            num = 0
            result *= stack.pop()
            result += stack.pop()

    result += sign * num
    return result

1. Digit accumulation. When you see a digit, you build the number by multiplying the current value by 10 and adding the new digit. This handles multi-digit numbers like 42 or 123.

2. Plus and minus. When you hit + or -, you finalize the current number by adding sign * num to result, reset num to 0, and set sign for the next number.

3. Opening parenthesis. Push result and sign onto the stack, then reset both. This starts a fresh scope for the subexpression inside the parentheses.

4. Closing parenthesis. Finalize the current number, then pop the sign (multiply it into result) and pop the saved result (add it). This merges the inner result back into the outer computation.

5. Final flush. After the loop, there may be a trailing number that was never finalized. The last line result += sign * num handles that.

Step-by-step walkthrough

Complexity analysis

You cannot do better than O(n) time because every character must be examined at least once. The solution is optimal.

Building blocks

1. Stack-based scope management. The pattern of pushing state when entering a scope and popping when leaving is foundational. You see it in compilers, interpreters, and many parsing problems. Whenever a problem involves nested structures, this push/pop pattern should come to mind.

2. Running accumulator with sign tracking. Instead of building a full parse tree, you keep a running total and a sign variable. This avoids recursion and keeps the code linear. The same technique works for any expression involving only addition and subtraction.

3. Multi-digit number parsing. The num = num * 10 + int(ch) idiom for building numbers from individual characters is a reusable primitive that appears in string-to-integer, atoi, and many calculator problems.

Edge cases

• Single number with no operators. "42" should return 42. The final flush after the loop handles this correctly.
• Leading spaces and spaces between tokens. " 3 + 5 " must work. Spaces are simply skipped since they do not match any branch in the if/elif chain.
• Nested parentheses. "((1+2))" should return 3. Each layer of parentheses pushes and pops from the stack, and the result propagates correctly through multiple levels.
• Unary minus at the start. "-1 + 2" should return 1. Since result starts at 0 and sign starts at +1, the leading minus sets sign = -1 after adding 0 * 0 to result, which is harmless.
• Subtraction of a parenthesized group. "10 - (3 + 2)" should return 5. The minus before the parenthesis sets sign = -1, which gets pushed onto the stack and applied when the closing parenthesis pops it.

From understanding to recall

The Basic Calculator algorithm is not conceptually difficult once you see the push/pop pattern for parentheses. But the details matter: the order of pushes and pops, when to flush the current number, how to handle the sign correctly. These are exactly the kind of details that slip away under pressure.

Spaced repetition locks them in. You type the solution from scratch at increasing intervals, and each time you reinforce the exact sequence of operations. After a few rounds, the code flows naturally. You do not need to re-derive the algorithm in an interview because your fingers already know it.

Related problems

• Evaluate Reverse Polish Notation uses the same stack-based evaluation approach, but with postfix notation instead of infix with parentheses
• Min Stack extends the stack data structure with O(1) minimum tracking, reinforcing the push/pop mechanics central to this problem
• Valid Parentheses is the simpler version of parenthesis handling, using a stack to match openers and closers without any arithmetic