Evaluate a Scoped Lisp Expression

Problem Statement

Implement an evaluator for a mini Lisp-like language. You are given a string expression representing a syntactically valid expression. Evaluate the expression and return its integer result.

An expression can take one of the following forms:

1. Integer Literal: A sequence of digits, optionally prefixed with - (e.g., 42, -7).
2. Variable: A sequence of lowercase English letters (e.g., x, foo). Its value is looked up in the current scope.
3. Addition: (add e1 e2) evaluates expression e1 and expression e2, returning their sum.
4. Multiplication: (mult e1 e2) evaluates expression e1 and expression e2, returning their product.
5. Let Binding: (let v1 e1 v2 e2 ... vn en expr) binds variable v1 to the evaluation of e1, then v2 to the evaluation of e2, and so forth sequentially. Finally, it evaluates and returns expr. Variable bindings inside a let block are local to that block and shadow any bindings with the same name in enclosing scopes.

Function Signature

def evaluate(expression: str) -> int:
    pass

Constraints

• 1 <= len(expression) <= 2000
• expression is syntactically valid and balanced with spaces separating tokens, except possibly immediately adjacent to parentheses (e.g., (add 1 2)).
• Variable names consist only of lowercase English letters.
• The result of any arithmetic operation and intermediate computation fits within a standard 32-bit signed integer.
• All variables referenced are guaranteed to be bound in the current or an outer scope.

Examples

Example 1:

Input: expression = "(let x 2 (mult x 5))"
Output: 10
Explanation:
x is assigned 2. The final expression evaluates (mult 2 5) = 10.

Example 2:

Input: expression = "(let x 3 (let x 4 (add x 5)))"
Output: 9
Explanation:
The inner let shadows the outer x with the value 4. (add 4 5) evaluates to 9.

Example 3:

Input: expression = "(let a (add 1 2) b (mult a 2) (add a b))"
Output: 9
Explanation:
First, a is bound to 3. Then, b is bound to (mult 3 2) = 6. Finally, (add 3 6) evaluates to 9.