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.
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
), callcalculateon 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"
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/ORprecedence use the same deferral:ORwaits whileANDbinds. - 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 / 2must be-3. In Python useint(a / b), nota // 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 is0and the operator is+. A-after another operator (2*-3) needs extra handling. - Multi-digit numbers.
num = num * 10 + digitmust accumulate across characters; a per-characterint(ch)silently breaks on12. - 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
- Delay the low-precedence work.
+and-push and wait;*and/resolve on the spot. - Push signed terms, so subtraction is addition and the final answer is a plain sum.
- Track the operator before the number. That single variable is what makes the loop uniform.
- A bracketed group is an uncomputed number: recurse or push the context, but reuse the same routine.
- Truncate toward zero, and say so before the interviewer asks.
- 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.