Parse Lisp Expression
You are given a string expression representing a Lisp-like expression. Return the integer value of expression.
The syntax for these expressions is as follows:
- An expression is either an integer, a let expression, an add expression, a mult expression, or an assigned variable. Expressions always evaluate to a single integer.
- An integer can be positive or negative.
- A let expression takes the form
"(let v1 e1 v2 e2 ... vn en expr)", whereletis always the string"let". There are one or more pairs of alternating variables and expressions, meaning that the first variablev1is assigned the value of expressione1, the second variablev2is assigned the value of expressione2, and so on sequentially. The value of this let expression is the value of the final expressionexpr. - An add expression takes the form
"(add e1 e2)", whereaddis always the string"add". There are always two expressionse1ande2, and the result is the sum of the evaluations ofe1ande2. - A mult expression takes the form
"(mult e1 e2)", wheremultis always the string"mult". There are always two expressionse1ande2, and the result is the product of the evaluations ofe1ande2. - A variable starts with a lowercase letter, followed by zero or more lowercase letters or digits. The names
"add","let", and"mult"are protected and will never be used as variable names. - Scope is determined by parentheses. When a variable name is evaluated, the innermost scope in the current context is checked first, then outer scopes are checked sequentially.
It is guaranteed that every expression is legal and evaluates to an integer.
Example 1
Input
expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"Output
14In
(add x y), the innermost scope assigns x = 3, so the result is 3 + 4 = 7, and the outer multiplication gives 2 * 7 = 14.Example 2
Input
expression = "(let x 3 x 2 x)"Output
2Assignment in let statements is processed sequentially, so
x is reassigned from 3 to 2 before being evaluated.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.