Parsing And Expression Evaluation

What's being tested

These problems test recursive descent parsing and expression evaluation under strict syntax rules. Interviewers are probing whether you can tokenize input, handle operator precedence, parentheses, unary operators, Lisp-style nested forms, lexical scoping, and invalid-input detection without turning the code into ad hoc string hacks.

Patterns & templates

• Tokenizer first — implement nextToken() or scan with index i; distinguish numbers, identifiers, operators, (, ), and whitespace in O(n) time.

• Recursive descent parser — use functions like parseExpr(), parseTerm(), parseFactor() for arithmetic precedence; each function consumes exactly the tokens it owns.

• Stack-based arithmetic evaluator — for + - * /, maintain current sign/term stack; parentheses can recurse or push previous state.

• Lisp evaluator template — parse forms like (let x 2 (add x 3)) recursively; evaluate operator, then operands, while advancing a shared index.

• Scoped environments — model variable bindings with Map<String, Deque<Integer>> or copy-on-write Map; push on entry, pop on exit to preserve lexical scope.

• Validation as parsing invariant — reject unexpected EOF, extra trailing tokens, missing ), empty expressions, invalid identifiers, and operator arity mismatches immediately.

• Complexity target — aim for O(n) time over input length and O(d + v) space, where d is nesting depth and v active bindings.

Common pitfalls

Pitfall: Treating parsing as repeated substring() splitting often breaks on nested parentheses and can degrade to O(n^2).

Pitfall: Forgetting unary - makes expressions like -3, 1*-2, or (- x) fail despite valid syntax.

Pitfall: Using one global variable map for Lisp let leaks inner bindings into outer scopes; use scoped push/pop or copied environments.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.