Expression Evaluation

What is this?

Read 2 + 3 * 4 left to right. At the + you cannot commit, because whatever follows the 3 might bind more tightly — and it does. So the 2 waits. This is the entire problem: an operator of lower precedence has to sit and wait to find out how much of what follows belongs to it.

The trick that makes it easy is refusing to think about precedence as a table of rules. Instead, keep a stack of terms that will eventually be added, and let high-precedence operators modify the top of that stack in place.

💡 Fun fact: the "push signed terms, resolve * and / immediately, sum at the end" technique means you never build a parse tree, never convert to postfix, and never write a precedence table — yet it produces exactly the same answer as a full expression parser for this grammar. It is a small, satisfying demonstration that the stack of pending additions is the parse tree, flattened.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: track the operator that came before the number you just read. + and - push a signed term; * and / reach back and combine with the top of the stack. Adding everything up at the end applies precedence for free.

1. The template

def calculate(s: str) -> int:
    stack, num, op = [], 0, '+'          # a leading '+' makes the first number uniform
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (not ch.isdigit() and ch != ' ') or i == len(s) - 1:
            if   op == '+': stack.append(num)
            elif op == '-': stack.append(-num)
            elif op == '*': stack.append(stack.pop() * num)
            elif op == '/': stack.append(int(stack.pop() / num))   # truncate toward zero
            num, op = 0, ch
    return sum(stack)

Three details carry the whole thing. The op variable holds the previous operator, so a number is only committed once you know what precedes it. The i == len(s) - 1 clause flushes the final number, which no operator follows. And division truncates toward zero, not floor — -7 // 2 is -4 in Python but the expected answer is -3, so int(a / b) is the correct spelling.

2. Nesting

Parentheses do not need a second mechanism. When you meet (, you are starting a brand-new expression whose value becomes a single number in the outer one — which is exactly the routine you already have. Two ways to say that:

• Recurse. Find the matching ), call calculate on the substring, and treat the result as a number. Simple to explain, though naive substring slicing costs extra memory.
• Push the context. On ( push the current stack and pending operator; on ) resolve the inner stack to a number and merge it into the restored outer context. This is what recursion does under the hood, made explicit.

Either way, the insight worth stating out loud is that a bracketed group is just a number you have not computed yet.

3. A 30-second worked example

"2-3*4+5"

read 2, op='+'   → push  2            stack=[2]
read 3, op='-'   → push -3            stack=[2,-3]
read 4, op='*'   → pop -3, push -12   stack=[2,-12]
read 5, op='+'   → push  5            stack=[2,-12,5]
                                       sum = -5

Notice the * applied to -3, not to 3. Pushing the signed term is what makes precedence and subtraction interact correctly without any special handling — a subtraction is simply the addition of a negative.

4. Where you'll actually meet this

• Spreadsheet formula engines. Every cell formula is parsed and evaluated with precedence, and the simplest correct implementations look like this.
• Query and rule engines. Filter expressions with AND/OR precedence use the same deferral: OR waits while AND binds.
• Configuration and template languages. Arithmetic inside templating systems is typically a small evaluator of exactly this shape.
• Calculators and REPLs. The obvious one, and still the standard interview proxy for "can you write a small language".
• Compilers. Precedence climbing and shunting-yard are the general versions; this template is the special case that fits on a whiteboard.

5. Problems in this chapter

▶ Basic Calculator II

Evaluate an expression with + - * / and no parentheses. The template above, with integer division truncating toward zero.
Pattern: signed-term stack with immediate high-precedence resolution. Target: O(n) time, O(n) space.

▶ Basic Calculator III

Adds nested parentheses to the same grammar. Either recurse on the substring or push the outer context — but do not write a second evaluator.
Pattern: the same template plus context suspension. Target: O(n) time, O(n) space.

6. Common pitfalls 🚫

• Flooring instead of truncating. -7 / 2 must be -3. In Python use int(a / b), not a // b.
• Forgetting to flush the last number. Nothing follows it, so the loop must handle end-of-string explicitly.
• Applying * to the unsigned number. Push signed terms and the sign takes care of itself.
• Handling spaces late. Skip them when accumulating digits, but do not let a space reset the pending operator.
• Treating unary minus as subtraction. A leading - (or one just after () needs an implicit 0 before it.
• Multi-digit numbers. num = num * 10 + digit must accumulate across characters — a per-character int(ch) silently breaks on 12.
• Writing a separate branch for parentheses. They are the same expression one level down; a second code path is where bugs breed.

7. Key takeaways

1. Delay the low-precedence work. + and - push and wait; * and / resolve on the spot.
2. Push signed terms, so subtraction is addition and the final answer is a plain sum.
3. Track the operator before the number. That single variable is what makes the loop uniform.
4. A bracketed group is an uncomputed number — recurse or push the context, but reuse the same routine.
5. Truncate toward zero, and say so before the interviewer asks.
6. Why interviewers like it: it is a miniature language implementation. It shows whether you can handle precedence, nesting, unary operators and integer-division semantics without flailing.

Order: Basic Calculator II → Basic Calculator III.