Parse and evaluate nested expressions with validation

Design and implement a parser/evaluator for a parenthesized expression language where the input string may be invalid. The language uses spaces as token separators and parentheses for grouping. Supported operators: sum, prod, set. Semantics: (sum e1 e2 ... ek) returns the sum of k>=2 subexpressions; (prod e1 e2 ... ek) returns the product of k>=2 subexpressions; (set x v body) binds variable x to the value of expression v within body and any nested scopes (lexical scoping, inner bindings shadow outer ones). Tokens: integer = optional leading '-' followed by digits; variable = lowercase letter followed by zero or more lowercase letters or digits. Implement a function evaluate(expr: string) -> int that computes the value if the expression is valid; otherwise it must report an error (e.g., throw/return InvalidExpression). The evaluator must: handle arbitrary nesting and extra spaces; support negative integers; maintain proper lexical scoping; and detect errors including mismatched or missing parentheses, unknown operators, wrong arity (e.g., set must have exactly 3 arguments with the first being a variable), undefined variable references, malformed numbers, empty expressions, and 32-bit signed integer overflow. Constraints: length(expr) <= 1e5, maximum nesting depth <= 1e4. Provide and explain two approaches (recursive descent vs. iterative stack-based) and analyze time/space complexity in terms of n = length(expr). Follow-ups: extend set to support multiple bindings like (set x 1 y 2 body); add a division operator with integer truncation and division-by-zero handling.