Expression Parsing and Evaluation for Google Coding

What's being tested

Expression parsing and evaluation problems test your ability to tokenize input, apply operator precedence and associativity, and produce a correct evaluation plan (either AST or stack-based). Interviewers probe for robust handling of edge cases (unary operators, whitespace, parentheses) and for an algorithmic solution with clear time/space bounds.

Patterns & templates

• Shunting-yard algorithm — convert infix to Reverse Polish Notation (RPN) in O(n) time, using an operator stack and output queue.

• RPN evaluation — single-pass stack-based evaluator: push numbers, pop operands on operator, O(n) time and O(n) extra space.

• Recursive descent parser — implement grammar functions like parseExpression, parseTerm, parseFactor to respect precedence and parentheses.

• Pratt / precedence-climbing parser — compact alternative to recursive descent for many precedence levels, avoid duplicating code per level.

• Tokenizer / lexer — produce numeric tokens, operators, parentheses; handle multi-digit numbers, decimals, and identifiers if needed.

• Unary vs binary handling — detect unary minus/plus by previous token type (start, (, or operator), treat as high-precedence unary operator.

• AST construction — build nodes (Op, Num) if transformations or repeated evaluations needed; evaluate via post-order traversal.

• Precision & types — decide integer vs floating semantics up front; use long/BigInteger or decimal libraries for overflow/precision guarantees.

Common pitfalls

Pitfall: Confusing unary and binary minus — treat -3 and a - 3 differently when tokenizing/parsing.

Pitfall: Wrong associativity for exponentiation — ^ is usually right-associative; mishandling produces incorrect results.

Pitfall: Not validating tokens/stack state — failing to detect malformed expressions leads to crashes or silent wrong answers.

Practice these

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