Parsing And Expression Evaluation
Asked of: Software Engineer
Last updated

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 indexi; distinguish numbers, identifiers, operators,(,), and whitespace inO(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-writeMap; 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 andO(d + v)space, wheredis nesting depth andvactive bindings.
Common pitfalls
Pitfall: Treating parsing as repeated
substring()splitting often breaks on nested parentheses and can degrade toO(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
letleaks 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.
Featured in interview prep guides
Practice questions
Related concepts
- Expression ParsingCoding & Algorithms
- String Parsing, Tokenization, And ValidationCoding & Algorithms
- Command Parsing And Predicate EvaluationCoding & Algorithms
- String Parsing, Palindromes, And NormalizationCoding & Algorithms
- String Processing, Parsing, And Output FormattingCoding & Algorithms
- Coding, Data Structures, And Parsing