Evaluate a Variadic Addition or Subtraction Expression

Problem Statement

Implement an evaluator for prefix-style variadic expressions. An expression is represented either as a single integer or as a list where the first element is an operator string ("+" or "-") and all subsequent elements are operands. Operands can be integers or nested expressions.

The operators behave as follows:

• "+": Computes the sum of all evaluated operands. If no operands are provided (["+"]), the result is 0.
• "-": If given a single operand, it computes the negation (-operand). If given two or more operands, it subtracts all subsequent evaluated operands from the first in left-associative order (e.g., ["-", a, b, c] evaluates to (a - b) - c). If given zero operands (["-"]), it should raise a ValueError.

Your implementation should validate the input and raise a ValueError if:

• An expression list is empty.
• The first element of an expression list is not a supported operator.
• Any operand is neither an integer nor a valid expression list.

Function Signature

def evaluate(expr: int | list) -> int:
    pass

Examples

Example 1:

expr = ["+", 1, 2, 3, 4]
# Output: 10
# Explanation: 1 + 2 + 3 + 4 = 10

Example 2:

expr = ["-", 10, 2, 3]
# Output: 5
# Explanation: (10 - 2) - 3 = 5

Example 3:

expr = ["-", ["+", 5, 5], ["-", 3]]
# Output: 13
# Explanation:
# ["+", 5, 5] evaluates to 10.
# ["-", 3] is unary negation, evaluating to -3.
# ["-", 10, -3] evaluates to 10 - (-3) = 13.

Constraints

• The total number of elements across all nested lists is at most 10^5.
• Integers are standard 32-bit signed integers.
• Maximum nesting depth is at most 1000.
• Time complexity must be O(N) where N is the total number of tokens/elements.
• Auxiliary space complexity must be O(D) where D is the maximum nesting depth.