Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Basic Calculator
• Main tags: Math, String, Stack, Recursion

What the problem is really asking

The input is a string expression that contains non-negative integers, +, -, parentheses, and spaces. The task is to return the final numeric value without using Python’s built-in expression evaluator.

The hard part is not addition or subtraction. The hard part is handling nested parentheses while preserving the correct sign in front of each parenthesized subexpression.

Because the expression only has + and -, each parenthesis level can be evaluated as a simple running total. There is no operator precedence problem from * or /. That observation makes the optimal solution much simpler than it first appears.

The key idea

At any moment, the evaluator only needs to know four things:

• the running total for the current parenthesis level
• the sign that should be applied to the next number or subexpression
• the number currently being parsed
• the saved outer contexts for any open parentheses

When a digit is read, it extends the current number.

When a + or - is read, the current number is committed into the running total using the current sign, and then the sign is updated for whatever comes next.

When a ( is read, the current context is paused. The evaluator pushes the current total and current sign onto a stack, then starts a fresh running total for the new inner expression.

When a ) is read, the inner expression is complete. Its total becomes one number from the perspective of the outer expression, so the evaluator pops the saved context and combines them:

outer_total + sign_before_parentheses * inner_total

That is the entire trick.

How to derive the optimal solution

The clean interview path usually looks like this:

1. Start with the obvious observation that the expression must be scanned from left to right because multi-digit numbers matter.
2. Notice that with only + and -, a single parenthesis level can be evaluated with a running total and a pending sign.
3. Realize that parentheses do not require a full expression tree. They only require the current state to be saved and restored later.
4. Use a stack to store the outer state whenever a ( appears.
5. When a ) appears, treat the finished inner result as one signed value and fold it back into the outer state.

That leads directly to an O(n) time solution, because each character is processed once and each parenthesis context is pushed and popped once.

A small walkthrough

Consider 8 - (3 + (2 - 1)).

The evaluator first sees 8, then -, so the outer running total becomes 8 and the next sign becomes negative.

When ( appears, it saves (8, -1) on the stack and starts evaluating the inside from scratch.

Inside that first pair of parentheses, it reads 3 + ..., so the inner running total becomes 3.

Then it reaches another (. It saves (3, +1) and evaluates 2 - 1, which becomes 1.

Now it closes the inner parentheses. The saved (3, +1) means the result becomes 3 + 1 * 1 = 4.

Then it closes the outer parentheses. The saved (8, -1) means the final result becomes 8 + (-1) * 4 = 4.

The stack is not storing every token. It is only storing the minimum state needed to resume the outer calculation.

Python solution

from typing import List, Tuple


ContextFrame = Tuple[int, int]


def combine_parenthesized_value(
    outer_total: int,
    sign_before_parentheses: int,
    inner_total: int,
) -> int:
    """
    Fold a completed parenthesized expression back into the surrounding level.
    """
    return outer_total + sign_before_parentheses * inner_total


def evaluate_basic_calculator(expression: str) -> int:
    """
    Evaluate an expression containing:
    - non-negative integers
    - '+'
    - '-'
    - '('
    - ')'
    - spaces

    The algorithm scans left to right. Each parenthesis level keeps its own
    running total, and a stack stores the outer contexts that need to be resumed
    after the inner expression ends.
    """
    current_total = 0
    pending_sign = 1
    current_number = 0
    number_in_progress = False
    context_stack: List[ContextFrame] = []

    def commit_current_number() -> None:
        nonlocal current_total, current_number, number_in_progress

        if not number_in_progress:
            return

        current_total += pending_sign * current_number
        current_number = 0
        number_in_progress = False

    for character in expression:
        if character.isdigit():
            current_number = current_number * 10 + int(character)
            number_in_progress = True
            continue

        if character == " ":
            continue

        if character in "+-":
            commit_current_number()
            pending_sign = 1 if character == "+" else -1
            continue

        if character == "(":
            # Pause the outer expression. The inner expression starts fresh,
            # but when it ends its value must still be multiplied by the sign
            # that appeared immediately before this parenthesis.
            context_stack.append((current_total, pending_sign))
            current_total = 0
            pending_sign = 1
            current_number = 0
            number_in_progress = False
            continue

        if character == ")":
            commit_current_number()
            outer_total, sign_before_parentheses = context_stack.pop()
            current_total = combine_parenthesized_value(
                outer_total,
                sign_before_parentheses,
                current_total,
            )
            continue

        raise ValueError(f"Unexpected character: {character}")

    commit_current_number()
    return current_total


class Solution:
    def calculate(self, s: str) -> int:
        return evaluate_basic_calculator(s)

Why this works

Every time the evaluator is inside one parenthesis level, the remaining work is just signed addition of numbers and completed subexpressions. That means a running total plus a pending sign is enough.

The only extra complication is that a parenthesized result must be inserted back into the outer expression with the sign that appeared before the (. Saving (outer_total, sign_before_parentheses) on the stack preserves exactly that information and nothing more.

Because each character is read once, each context is pushed once, and each context is popped once, the algorithm runs in O(n) time. The stack uses O(n) space in the worst case when the parentheses are deeply nested.

Interview follow-ups

Can this be solved recursively instead of iteratively?

Yes. A recursive parser can treat each ( as the start of a new subproblem and return when it reaches the matching ). That approach is also O(n) time, and many people find it conceptually elegant because the call stack mirrors the nesting structure of the expression. The main tradeoff is practical rather than theoretical: the iterative stack solution is usually safer in Python for very deep nesting, and it makes the saved state completely explicit during an interview.

What changes if * and / are added?

Then a single running total is no longer enough, because multiplication and division have higher precedence than addition and subtraction. The usual next step is to keep a stack or a last_term value for the current level so multiplication and division can be resolved before the final sum is produced. Parentheses can still be handled with the same general idea of saving outer context, but each context now has to preserve enough information to respect operator precedence when control returns to the outer expression.

How does the solution handle unary minus such as -(2 + 3)?

It works naturally once the sign is treated as applying to the next value, whether that value is a number or an entire parenthesized expression. In -(2 + 3), the parser sees - and sets the pending sign to -1. When ( appears, that sign is saved with the outer context. After the inner expression evaluates to 5, the combination step computes 0 + (-1) * 5, which is -5. No special extra case is needed beyond the normal sign-handling logic.

Why is this considered hard if the code is fairly short?

The difficulty is mostly in modeling the state correctly, not in writing many lines of code. Candidates often get lost on when to commit a number, what exactly to push onto the stack, or how to combine the inner result when ) appears. The interviewer is usually testing whether the candidate can reduce a nested parsing problem into a clean state machine with a stack, rather than whether the candidate can memorize a long implementation.

Practical takeaway

This problem becomes manageable as soon as it is reframed from “parse a whole math expression” into “maintain one running total per parenthesis level and save outer context on a stack.”

That pattern is reusable. Whenever an expression language is simple inside one nesting level, the main job is often not full parsing but careful context management.