Evaluate an Integer Arithmetic Expression String With Operator Precedence
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
Input: s = "1-2-3"
Output: -4
```
Subtraction is applied from left to right: `1 - 2` is -1, and `-1 - 3` is -4.
Overview: A coding problem to evaluate a string expression of non-negative integers with addition, subtraction, multiplication and integer division, respecting operator precedence and left-to-right order, with no parentheses and no eval. It tests parsing, precedence handling and truncating integer division.
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`.
### 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, read as a base-10 integer. Spaces may appear before or after any number or operator, but never inside a number.
- No division by zero occurs.
Return the value of the whole expression as an integer. Every intermediate result and the final result lie between `-2^31` and `2^31 - 1`, so no value exceeds `2^31 - 1` and a 32-bit `int` return type is enough in Java and C++.
### Examples
**Example 1**
```text
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**
```text
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.
### 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`.
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
Input: ('14 - 3*4 / 5 + 2',)
Expected Output: 14
Explanation: Source example 1: 3*4 = 12, 12 / 5 truncates to 2, so 14 - 2 + 2 = 14.
Input: (' 7 / 2 * 3 ',)
Expected Output: 9
Explanation: Source example 2: left to right, 7 / 2 = 3 then 3 * 3 = 9; leading and trailing spaces are ignored.
Hints
- Because `*` and `/` take precedence over `+` and `-`, a run of numbers joined by `*` and `/` must be fully evaluated, left to right, before it is added to or subtracted from anything.
- A number is a maximal run of digits and spaces never split one, so keep consuming digits until a space, an operator or the end of the string; make sure whatever is still pending when the string ends is counted.
- There is no unary minus and every number is non-negative, so a `-` applies to the entire `*`/`/` run that follows it. Check `10 - 7 / 2`: the division truncates to 3 first, giving 7.