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.
This approach uses a recursive function to evaluate the expression. It leverages the call stack to manage the scope of variables and interpret the expression inside-out. With every encountered sub-expression, the function evaluates and returns the result. It's well-suited for problems where the expression can be broken recursively.
This solution uses a recursive function eval_expr that processes a tokenized version of the input expression string. It maintains a scope using a dictionary, allowing nested variable bindings. The recursion allows processing of nested expressions, and each part of the expression (let, add, mult) is interpreted and computed recursively. Handling of parentheses ensures the correct parsing of expressions.
Time Complexity: O(n), where n is the length of the expression because we should parse each character at least once.
Space Complexity: O(n) in the worst case due to recursion stack and scope storage.
This approach uses an iterative process with stacks to evaluate the expression. It processes tokens sequentially and uses multiple stacks to manage the current values, scopes, and operations, providing an efficient and clear way to manage nested and complex expressions.
The JavaScript solution employs a stack-based approach to manage parsing and interpretation iteratively because JavaScript handles iterables effectively through such mechanisms. Multiple stacks are used to maintain separate components, involving scopes (for variable state), operators (for the current operational context), and tokenStack (for parsed tokens and results). This approach achieves efficient parsing and allows handling nested scopes easily.
JavaScript
C++
Time Complexity: O(n), where n is the length of the expression.
Space Complexity: O(n) for the stacks used in parsing.
| Approach | Complexity |
|---|---|
| Recursive Parsing | Time Complexity: O(n), where n is the length of the expression because we should parse each character at least once. |
| Iterative Parsing with Stacks | Time Complexity: O(n), where n is the length of the expression. |
| Default Approach | — |
| 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. |
花花酱 LeetCode 736. Parse Lisp Expression - 刷题找工作 EP119 • Hua Hua • 6,732 views views
Watch 9 more video solutions →Practice Parse Lisp Expression with our built-in code editor and test cases.
Practice on FleetCode