p96 — Basic Calculator II

Source: LeetCode 227 · Medium · Topics: Stack, String Parsing, Operator Precedence Companies (2024–2025): Google (high), Meta (high), Amazon (medium), Microsoft (medium) Loop position: The canonical parsing problem. Tests whether you can hand-roll a tokenizer + precedence-aware evaluator without leaning on eval.

1. Quick Context

Evaluate a string expression with + - * / (integer division truncating toward zero) and non-negative integers. No parentheses.

Two solutions:

  1. Stack of operands, current-op deferred: read each number; based on the previous operator, push, subtract, multiply-with-top, or divide-with-top. Final answer = sum of stack.
  2. Two-pass (tokenize → reduce): tokenize, then collapse * / first pass, sum second pass.

Follow-up (LC 224): add parentheses → recursive descent or stack-of-stacks.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/basic-calculator-ii/

STOP. 30-min timer. No eval. Handle multi-digit and leading/trailing spaces.

3. Prerequisite Concepts

  • Tokenization basics.
  • Operator precedence (*/ before +-).
  • Integer division semantics in Python (// rounds toward -inf; for truncation toward zero use int(a/b) or sign-careful logic).

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Evaluate infix expression with precedence; integer division truncates toward zero.

2. Clarify: Negative results from 7-3*2? Yes, 1. Division truncation: -3 / 2 → -1, not -2.

3. Examples: "3+2*2" → 7. " 3/2 " → 1. " 3+5 / 2 " → 5. "14-3/2" → 13.

5. Brute: Python eval (forbidden) or shunting-yard.

6. Target: O(n) time, O(n) space (stack of operands).

7. Pattern: Single-pass deferred-operator stack.

8. Develop: see solution.py.

9. Test: all four ops; multi-digit; leading/trailing spaces; embedded spaces; single number; chained * /; truncation of negative quotients.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The “deferred operator” pattern

Track prev_op (initially +) and cur_num (the number being built). When you hit an operator or end-of-string, apply prev_op to cur_num against the stack:

  • +: stack.append(cur_num)
  • -: stack.append(-cur_num)
  • *: stack.append(stack.pop() * cur_num)
  • /: stack.append(int(stack.pop() / cur_num))

Then prev_op = current operator, cur_num = 0.

Final answer = sum(stack).

Why it works: +/- are stored as-is (commute with addition). *// reduce immediately with the previous operand (higher precedence). At end, the stack contains only additively-combinable terms.

6.2 Integer division — truncation toward zero

Python’s // rounds toward -inf: -3 // 2 == -2. LC requires truncation: -3 / 2 → -1. Use int(a / b) (float division then truncate) or -(-a // b) when a < 0.

In real C/Java/Rust, integer / already truncates toward zero. This Python-specific gotcha is a common interview trap.

6.3 With parentheses (LC 224)

Two clean approaches:

  1. Recursive descent: parse_expr / parse_term / parse_factor, where parse_factor recurses on (.
  2. Stack with sign accumulator: maintain running result and sign; on (, push (result, sign); on ), pop and combine.

6.4 General expression parsing — shunting yard

Dijkstra’s shunting-yard algorithm converts infix to postfix (RPN) using two stacks (output + operator). Evaluate postfix with a single operand stack. The deferred-operator trick is a specialized inlining for the 4-op case.

6.5 Family: parsing / expression eval

  • LC 227 Basic Calculator II (this).
  • LC 224 Basic Calculator (with parens, +/-).
  • LC 772 Basic Calculator III (+ parens + */).
  • LC 770 Basic Calculator IV (symbolic).
  • LC 394 Decode String (stack-based parsing).
  • LC 726 Number of Atoms (recursive descent on chemistry).

7. Anti-Pattern Analysis

  1. eval(s) — disallowed; also unsafe in production.
  2. Python // for negative quotients — wrong; must truncate toward zero.
  3. Process operator immediately when seen — forces a state machine that fails on 3 + 5 * 2 / 4.
  4. Forget to flush cur_num at end-of-string — last number missed.
  5. Skip whitespace ad-hoc — clean is if c.isspace(): continue or if c == ' ' early-continue.
  6. Build cur_num with int(c) then cur_num * 10 + int(c) is right; using string concat cur_num + c then int(cur_num) works but allocates.

8. Skills & Takeaways

  • Deferred-operator stack pattern.
  • Truncation-toward-zero division in Python.
  • Tokenization while scanning.

9. When to Move On

  • Solve cold in 20 min.
  • Extend to parens (LC 224) cleanly.
  • Articulate shunting-yard generalization.

10. Company Context

  • Google: L5; expects clean parser + correctly handles negative truncation.
  • Meta: E5; favorite for “design but coding” round; often extended to parens mid-interview.
  • Amazon: L6.
  • Microsoft: L62/L63.

Strong: “Single-pass scan with a prev_op deferred-operator stack: +/- push signed, *// reduce against top. Final = sum(stack). O(n) time, O(n) space. Python: use int(a/b) to truncate toward zero on division.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
TokenizeBuggyColdClean+ streaming
PrecedenceMissesAfter hintDeferred-op+ shunting-yard
TruncationBugFixed afterCold+ cross-language semantics
Parens extNoneBuggySketch+ recursive descent cold

12. Level Delta

  • Mid (L4): Works on happy path; fails on -3/2 truncation.
  • Senior (L5): Cold solution + handles edge cases.
  • Staff (L6): + extends to parens + cites shunting-yard + production safety note (never eval user input).
  • Principal (L7+): + recursive-descent grammar in BNF + tokenizer/parser separation + recognizes as the foundation of all expression DSLs (formula bars in Excel, query languages, configuration languages).

13. Follow-up Q&A

Q1: Add parentheses. A1: Stack-of-stacks: on (, push current state (result, sign); on ), pop and combine. Or recursive descent (cleaner).

Q2: Add ^ (exponent, right-associative). A2: Shunting-yard with associativity flags; or precedence-climbing parser.

Q3: Symbolic variables (e.g., 2*x + 3)? A3: Build expression tree; defer evaluation; return AST.

Q4: Float arithmetic instead of integer. A4: Replace int(a/b) with a/b; tokenizer must accept decimal point.

Q5: Why is eval() dangerous in production? A5: Arbitrary code execution. Even sandboxed, leaks side effects, memory, CPU. Use a real parser.

14. Solution Walkthrough

See solution.py:

  • calculate — single-pass deferred-operator stack.
  • calculate_shunting_yard — infix → postfix → eval (general).
  • calculate_brute — uses Python AST (oracle).

15. Beyond the Problem

Principal code review: “Basic Calculator II is the smallest non-trivial parser problem. The Staff+ recognition is that you’re building, in miniature, the same machinery that powers every DSL in production: SQL parsers (PostgreSQL, DuckDB), spreadsheet formula engines (Excel, Google Sheets), templating engines (Jinja, Handlebars), configuration languages (HCL, Nginx config), regex compilers, and even shader languages. The lesson scales in three directions: (1) lexer/parser separation (tokenize first, parse second — keeps grammar clean), (2) precedence handling (deferred-op for fixed-precedence ops, precedence-climbing or Pratt parser for extensible grammars, shunting-yard for explicit infix→postfix), (3) evaluation strategy (eager eval vs build-AST-then-walk; the AST approach unlocks optimization passes, partial evaluation, JIT compilation). Production-grade parsers (ANTLR, tree-sitter, LLVM frontend) are ‘just’ large versions of this exercise. The principal-level skill is recognizing when to hand-roll (small grammar, performance-critical, no dependency wanted) vs use a parser generator (large grammar, frequent grammar changes, want LSP/syntax-highlighting support).”