Evaluate an Arithmetic Expression with Parentheses, Unary Minus and Four Operators

Evaluate an arithmetic expression given as a string and return its integer value. This covers the whole reported calculator series: addition and subtraction with parentheses and a leading minus sign, and multiplication and division with their usual precedence.

Function Signature

def evaluate(expression: str) -> int:

Rules

• The expression contains non-negative integer literals, the binary operators +, -, * and /, parentheses, and spaces. Spaces can appear between tokens but never inside a number.
• * and / bind more tightly than + and -. Operators of equal precedence are applied from left to right, and parentheses group as usual.
• - can also be unary, but only at the very start of the expression or directly after (, ignoring spaces. It negates the number or the parenthesized group that follows it. + is never unary.
• Division is integer division that truncates toward zero, so 7 / 2 is 3 and -7 / 2 is -3.
• Do not call a built-in expression evaluator such as eval.

Constraints

• 1 <= len(expression) <= 10^4
• The expression contains only digits, +, -, *, /, (, ) and spaces, and it is valid.
• No division by zero occurs.
• Every literal and every intermediate result lies between -2^31 and 2^31 - 1.
• Parentheses can be nested deeply, up to about half the length of the expression.

Examples

Example 1

Input: expression = "2 + 3 * (4 - 1) / 2"
Output: 6

3 * (4 - 1) is 9, 9 / 2 truncates to 4, and 2 + 4 is 6.

Example 2

Input: expression = "-(3 + 4) / 2"
Output: -3

The leading minus negates the group, giving -7, and -7 / 2 truncates toward zero to -3.

Example 3

Input: expression = "14 - 3 - (2 - (-5))"
Output: 4

Subtraction runs left to right: 14 - 3 is 11, the inner group 2 - (-5) is 7, and 11 - 7 is 4.