Evaluate an Integer Arithmetic Expression String With Operator Precedence

Given a string s that holds a valid arithmetic expression, return its integer value. The expression contains non-negative integers, the binary operators +, -, * and /, and spaces. Do not use a built-in facility that evaluates a string as code, such as eval.

Function Signature

def evaluate_expression(s: str) -> int:

Rules

• * and / take precedence over + and -.
• Operators of equal precedence are applied from left to right, so 8 - 3 - 2 is 3 and 8 / 2 * 2 is 8.
• / is integer division that truncates toward zero.
• There are no parentheses and no unary operators: the expression is a number, followed by zero or more pairs of an operator and a number.
• A number is a maximal run of decimal digits. Spaces may appear before or after any number or operator, but never inside a number.
• No division by zero occurs.

Constraints

• 1 <= len(s) <= 3 * 10^5
• s consists only of digits, '+', '-', '*', '/' and ' ', and it is a valid expression under the rules above.
• Every number in s is between 0 and 2^31 - 1.
• Evaluating with the rules above, every intermediate result and the final result lie between -2^31 and 2^31 - 1.

Examples

Example 1

Input: s = "14 - 3*4 / 5 + 2"
Output: 14

3*4 is 12, and 12 / 5 truncates to 2, so the expression becomes 14 - 2 + 2, which is 14.

Example 2

Input: s = " 7 / 2 * 3 "
Output: 9

/ and * are applied from left to right: 7 / 2 is 3, and 3 * 3 is 9. The leading and trailing spaces are ignored.

Example 3

Input: s = "1-2-3"
Output: -4

Subtraction is applied from left to right: 1 - 2 is -1, and -1 - 3 is -4.