Watch 10 video solutions for Parse Lisp Expression, a hard level problem involving Hash Table, String, Stack. This walkthrough by Hua Hua has 6,732 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string expression representing a Lisp-like expression to return the integer value of.
The syntax for these expressions is given as follows.
"(let v1 e1 v2 e2 ... vn en expr)", where let is always the string "let", then there are one or more pairs of alternating variables and expressions, meaning that the first variable v1 is assigned the value of the expression e1, the second variable v2 is assigned the value of the expression e2, and so on sequentially; and then the value of this let expression is the value of the expression expr."(add e1 e2)" where add is always the string "add", there are always two expressions e1, e2 and the result is the addition of the evaluation of e1 and the evaluation of e2."(mult e1 e2)" where mult is always the string "mult", there are always two expressions e1, e2 and the result is the multiplication of the evaluation of e1 and the evaluation of e2."add", "let", and "mult" are protected and will never be used as variable names.
Example 1:
Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" Output: 14 Explanation: In the expression (add x y), when checking for the value of the variable x, we check from the innermost scope to the outermost in the context of the variable we are trying to evaluate. Since x = 3 is found first, the value of x is 3.
Example 2:
Input: expression = "(let x 3 x 2 x)" Output: 2 Explanation: Assignment in let statements is processed sequentially.
Example 3:
Input: expression = "(let x 1 y 2 x (add x y) (add x y))" Output: 5 Explanation: The first (add x y) evaluates as 3, and is assigned to x. The second (add x y) evaluates as 3+2 = 5.
Constraints:
1 <= expression.length <= 2000expression.expression.Problem Overview: You receive a Lisp-style expression containing add, mult, and let operations. Variables can be assigned values and reused within nested scopes. The goal is to parse the string and evaluate the final integer result while respecting variable scope and nested parentheses.
Approach 1: Recursive Parsing (O(n) time, O(n) space)
This approach treats the expression as a recursive structure. Each time you encounter (, you parse the operation (add, mult, or let) and recursively evaluate its arguments. A hash map stores variable bindings for the current scope, and nested calls receive a copied or layered environment so inner assignments do not leak outward. For add and mult, recursively evaluate two operands. For let, iterate through variable-value pairs and update the environment before evaluating the final expression. Each character in the string is processed once, giving O(n) time complexity. The recursion stack and variable maps contribute O(n) space in the worst case when deeply nested expressions appear. This method maps directly to the grammar of the expression and is often the cleanest way to reason about nested evaluation using recursion and hash tables.
Approach 2: Iterative Parsing with Stacks (O(n) time, O(n) space)
An iterative parser replaces recursion with explicit stacks. Scan the string character by character and push tokens onto a stack whenever you encounter parentheses or operands. When a closing parenthesis appears, pop tokens until the matching opening parenthesis, evaluate the subexpression, and push the result back onto the stack. A secondary structure tracks variable scopes created by let operations so assignments remain valid only inside the current expression block. This design mimics how compilers evaluate nested expressions using stacks. Each token is pushed and popped at most once, so the runtime remains O(n). Space usage is also O(n) due to stacks and scope maps. This approach is useful if you want full control over parsing without relying on recursion depth.
Recommended for interviews: Recursive parsing is usually expected because the nested structure of Lisp expressions naturally forms a recursive evaluation tree. Interviewers want to see that you can manage variable scope correctly using a hash map and evaluate expressions as you descend into parentheses. The stack-based parser demonstrates deeper understanding of interpreters and expression evaluation but takes more implementation effort.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Parsing | O(n) | O(n) | Best for interview settings and when the expression structure maps naturally to recursion. |
| Iterative Parsing with Stacks | O(n) | O(n) | Useful when avoiding recursion depth limits or implementing interpreter-style parsing. |