Parse Lisp Expression - Video Solutions
花花酱 LeetCode 736. Parse Lisp Expression - 刷题找工作 EP119
Parse Lisp Expression - Video Solution
Watch 10 video solutions for Parse Lisp Expression, a hard level problem involving Hash Table, String, Stack. This walkthrough by Hua Hua has 6,745 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
- An expression is either an integer, let expression, add expression, mult expression, or an assigned variable. Expressions always evaluate to a single integer.
- (An integer could be positive or negative.)
- A let expression takes the form
"(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 variablev1is assigned the value of the expressione1, the second variablev2is assigned the value of the expressione2, and so on sequentially; and then the value of this let expression is the value of the expressionexpr. - An add expression takes the form
"(add e1 e2)"where add is always the string"add", there are always two expressionse1,e2and the result is the addition of the evaluation ofe1and the evaluation ofe2. - A mult expression takes the form
"(mult e1 e2)"where mult is always the string"mult", there are always two expressionse1,e2and the result is the multiplication of the evaluation of e1 and the evaluation of e2. - For this question, we will use a smaller subset of variable names. A variable starts with a lowercase letter, then zero or more lowercase letters or digits. Additionally, for your convenience, the names
"add","let", and"mult"are protected and will never be used as variable names. - Finally, there is the concept of scope. When an expression of a variable name is evaluated, within the context of that evaluation, the innermost scope (in terms of parentheses) is checked first for the value of that variable, and then outer scopes are checked sequentially. It is guaranteed that every expression is legal. Please see the examples for more details on the scope.
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 <= 2000- There are no leading or trailing spaces in
expression. - All tokens are separated by a single space in
expression. - The answer and all intermediate calculations of that answer are guaranteed to fit in a 32-bit integer.
- The expression is guaranteed to be legal and evaluate to an integer.
Approach Overview
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.
Complexity Analysis
| 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. |