Evaluate a Scoped Lisp Expression
Company: Attentive
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Evaluate a Scoped Lisp Expression
Implement:
```text
evaluateLisp(expression) -> integer
```
The input uses this grammar:
```text
expression := integer
| variable
| (add expression expression)
| (mult expression expression)
| (let variable expression ... variable expression expression)
```
An integer may be negative. A variable begins with a lowercase letter and then contains lowercase letters or digits. Tokens are separated by one or more spaces; parentheses delimit expressions.
`add` and `mult` evaluate their two operands. A `let` expression evaluates its variable-value pairs from left to right in the current nested scope, then evaluates its final expression. A later binding may refer to earlier bindings in the same `let`. Inner bindings shadow outer bindings only until the inner expression ends. The input is syntactically valid, and every evaluated variable is in scope.
Return the value of the complete expression. All intermediate values fit in a signed 64-bit integer.
## Constraints
- `1 <= expression.length <= 20,000`
- Nesting depth is at most 1,000.
## Examples
### Example 1
```text
expression = "(add 1 (mult -2 3))"
output = -5
```
### Example 2
```text
expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
output = 14
```
The inner `x` shadows the outer `x`, so the inner addition is 7 and the outer multiplication is `2 * 7`.
Overview: Implement an evaluator for a small Lisp-like language with addition, multiplication, sequential let bindings, nested scopes, and variable shadowing. The prompt defines a deterministic grammar, valid-input guarantees, signed integers, and two checked scoping examples.
Read the full Attentive Software Engineer interview experience this question came from