Evaluate an Integer Arithmetic Expression Written in Prefix (Polish) Notation

In prefix notation, also called Polish notation, every operator is written before its two operands, so parentheses are never needed. For example, the infix expression `(2 * 5) - (7 / -2)` is written as the token sequence `- * 2 5 / 7 -2`. Given the tokens of a valid prefix expression over integers, evaluate it and return its value. ### Function Signature ```python def evaluate_prefix(tokens: List[str]) -> int: ``` ### Rules - Each token is either an operator, exactly one of `"+"`, `"-"`, `"*"`, `"/"`, or a base-10 integer literal with an optional leading minus sign, such as `"-2"`. A token that is exactly `"-"` is always the subtraction operator. - Every operator is binary. It is followed by its first operand and then its second operand, and each operand is itself a complete prefix expression: either a single literal or another operator followed by its own operands. - `"-"` returns the first operand minus the second; `"/"` returns the first operand divided by the second. - Division is integer division that truncates toward zero: `7 / -2` is `-3` and `-7 / 2` is `-3`. - A single literal on its own is a valid expression. - The input always forms exactly one valid expression that uses every token, and no divisor ever evaluates to zero. - The result is a single integer, so there is exactly one correct answer. ### Constraints - `1 <= len(tokens) <= 10^4` - Every integer literal is between `-10^4` and `10^4` inclusive, with no leading `+` sign and no leading zeros. - Every intermediate result and the final result lie between `-2^31` and `2^31 - 1` inclusive. ### Examples **Example 1** ```text Input: tokens = ["+", "3", "4"] Output: 7 ``` The expression is `3 + 4`. **Example 2** ```text Input: tokens = ["-", "*", "2", "5", "/", "7", "-2"] Output: 13 ``` The first operand of `-` is `* 2 5`, which is 10. The second operand is `/ 7 -2`, which is -3 after truncating toward zero. The result is `10 - (-3) = 13`. **Example 3** ```text Input: tokens = ["/", "-", "-9", "6", "4"] Output: -3 ``` The first operand of `/` is `- -9 6`, which is -15. Dividing by 4 gives -3.75, which truncates toward zero to -3.