#736
Parse Lisp Expression
candidate master · 1390 · lc hard +32 · verified · 53.5% accepted · 499 likes · top 45%
Description
Evaluate a Lisp-style expression string and return its integer result. The grammar supports:
- Integer literals (positive or negative).
- Variable references — lowercase-letter-starting identifiers (excluding the reserved words "let", "add", "mult").
- (let v1 e1 v2 e2 ... expr) — binds each variable vi to the value of ei in sequence, then returns expr.
- (add e1 e2) — returns the sum of e1 and e2.
- (mult e1 e2) — returns the product of e1 and e2.
Variable lookup uses lexical scoping: the innermost enclosing let binding for a name takes precedence. All expressions are guaranteed valid.
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.
Code
1
2
3