The Parse Lisp Expression problem asks you to evaluate a simplified Lisp-like expression that supports let (variable binding), add (addition), and mult (multiplication) operations, with nested scopes. This hard coding problem requires recursive descent parsing with scoped variable lookup. The recursion, hash table, string, and stack interview pattern is the core.
Affirm, Amazon, and Google ask this because it tests recursive expression parsing — a skill directly relevant to compilers, interpreters, and DSL implementation. The ability to handle nested scopes with variable shadowing tests deep recursive design.
Recursive descent with scope stack. Parse the expression character by character. When encountering '(': parse the operator. For let: process (variable, value) pairs, binding variables in a new scope. For add/mult: recursively evaluate two sub-expressions and combine. Use a scope (hash map or stack) for variable lookup, supporting shadowing.
"(let x 2 (add x 1))".
"(let x 1 y 2 (add x y))": bind x=1, y=2. add(1,2)=3.
"(let x 2 (let x 3 x))": outer x=2, inner x=3. Inner expression returns 3.
let block ends.let expression's last token is a variable (return its value).Recursive descent parsing is a fundamental compiler technique. For this problem, the key is correct scope management: enter new scope on let, exit when done. Use a dictionary copied per scope or a stack of (var, value) pairs. Practice similar expression parser problems (calculator, basic interpreter) to build recursive parsing intuition. Each level of nesting = one recursive call.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Basic Calculator IV | Hard | Solve | |
| Parsing A Boolean Expression | Hard | Solve | |
| Decode String | Medium | Solve | |
| Ternary Expression Parser | Medium | Solve | |
| Number of Atoms | Hard | Solve |