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)", where let is always the string "let". There are one or more pairs of alternating variables and expressions, meaning that the first variable v1 is assigned the value of expression e1, the second variable v2 is assigned the value of expression e2, and so on sequentially. The value of this let expression is the value of the final expression expr.
  • An add expression takes the form "(add e1 e2)", where add is always the string "add". There are always two expressions e1 and e2, and the result is the sum of the evaluations of e1 and e2.
  • A mult expression takes the form "(mult e1 e2)", where mult is always the string "mult". There are always two expressions e1 and e2, and the result is the product of the evaluations of e1 and e2.
  • 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
Inputexpression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output14
In (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
Inputexpression = "(let x 3 x 2 x)"
Output2
Assignment 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.

Asked at 3 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate