</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Expression evaluation flowchart: the operator decides push or pop-and-combine (chalkboard)

Worth knowing: 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 gives 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 core 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. int(a / b) truncates correctly for 32-bit-sized values; the lessons use -(-a // b) for negative a, which avoids float rounding.


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, but the call depth grows with the nesting, and Python's default recursion limit is about 1,000.
  • 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, with the frames kept in a list you control.

Either way, the insight worth saying 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"

Expression evaluation worked trace of 2-3*4+5: stack stack 2,-3 then 2,-12 then 2,-12,5, sum -5 (chalkboard)

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. Includes an O(1)-space follow-up that replaces the stack with a running total and one open term.
Pattern: signed-term stack with immediate high-precedence resolution. Target: O(n) time, O(n) space (reducible to O(1)).

Basic Calculator III

Adds nested parentheses to the same grammar. Either recurse on the group or push the outer context onto a frame stack, but do not write a second evaluator. The lesson walks both approaches.
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. The problems here have no unary minus, but a leading - (or one just after () works because the pending number is 0 and the operator is +. A - after another operator (2*-3) needs extra handling.
  • 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.

Basic Calculator II

Core idea: Remember the operator that came before the number you just read. + and - push a signed term onto a stack; * and / pop the top term and combine it with the new number straight away. Summing the stack at the end gives you precedence without a parse tree or a precedence table.

Problem, rephrased

You're building the formula engine for a lightweight spreadsheet. A user types arithmetic into a cell, and your code must compute the value to display without handing the text to a built-in evaluator like eval(). The cell contents arrive as a string s: non-negative integers, the operators +, -, *, /, and stray spaces from careless typing. There are no parentheses and no unary minus.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.