Evaluate an Integer Expression with + - * / and No Parentheses
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement a basic calculator for expressions without parentheses. The source describes it only as "the basic version, without parentheses". This version uses the four operators `+`, `-`, `*` and `/` on non-negative integers.
Given the expression as a string, evaluate it and return the integer result.
### Function Signature
```python
def evaluate(expression: str) -> int:
```
### Rules
- The expression contains non-negative integer literals, the binary operators `+`, `-`, `*` and `/`, and spaces, which may appear anywhere and are ignored.
- `*` and `/` bind tighter than `+` and `-`. Operators of equal precedence are evaluated left to right.
- `/` is integer division that discards the fractional part (rounding toward zero).
- There are no parentheses and no unary operators, the expression is always valid, and division by zero never occurs.
- Do not use `eval` or a similar built-in expression evaluator.
### Constraints
- `1 <= len(expression) <= 3 * 10^5`
- `expression` consists of digits, `'+'`, `'-'`, `'*'`, `'/'` and `' '`, and contains at least one integer.
- Every integer literal is between `0` and `2^31 - 1`.
- Every intermediate result and the final result are between `-2^31` and `2^31 - 1`.
### Examples
**Example 1**
```text
Input: expression = "14 - 3 * 4 / 5"
Output: 12
```
`3 * 4 = 12`, then `12 / 5 = 2`, and `14 - 2 = 12`.
**Example 2**
```text
Input: expression = " 8 / 3 * 3 + 1"
Output: 7
```
`8 / 3 = 2`, then `2 * 3 = 6`, and `6 + 1 = 7`.
**Example 3**
```text
Input: expression = "2 - 3 - 4"
Output: -5
```
Subtraction is evaluated left to right: `(2 - 3) - 4`.
Overview: Evaluate an arithmetic expression string containing non-negative integers, plus, minus, times, integer division and spaces, but no parentheses, respecting operator precedence and left-to-right evaluation. Tests single-pass parsing, precedence handling and truncating integer division.
Implement a basic calculator for arithmetic expressions that contain no parentheses. The expression is given as a string made of non-negative integer literals, the binary operators `+`, `-`, `*` and `/`, and spaces. Evaluate it and return its integer value.
Implement `evaluate(expression)`, which returns the value of `expression` as an integer.
### Rules
- Spaces may appear anywhere in the expression and are ignored.
- `*` and `/` bind tighter than `+` and `-`. Operators of equal precedence are evaluated left to right, so `2 - 3 - 4` means `(2 - 3) - 4` and `8 / 3 * 3` means `(8 / 3) * 3`.
- `/` is integer division that discards the fractional part (rounds toward zero).
- There are no parentheses and no unary operators, the expression is always valid, and division by zero never occurs.
- Do not use `eval` or a similar built-in expression evaluator.
### Constraints
- `1 <= len(expression) <= 3 * 10^5`
- `expression` consists of digits, `'+'`, `'-'`, `'*'`, `'/'` and `' '`, and contains at least one integer.
- Every integer literal is between `0` and `2^31 - 1`.
- Every intermediate result and the final result are between `-2^31` and `2^31 - 1`, so no value exceeds `2^31 - 1` and the answer always fits in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: expression = "14 - 3 * 4 / 5"
Output: 12
```
`3 * 4 = 12`, then `12 / 5 = 2`, and `14 - 2 = 12`.
**Example 2**
```text
Input: expression = " 8 / 3 * 3 + 1"
Output: 7
```
`8 / 3 = 2`, then `2 * 3 = 6`, and `6 + 1 = 7`.
Constraints
- 1 <= len(expression) <= 3 * 10^5
- expression consists of digits, '+', '-', '*', '/' and ' ', and contains at least one integer.
- Every integer literal is between 0 and 2^31 - 1.
- Every intermediate result and the final result are between -2^31 and 2^31 - 1, so the answer fits in a signed 32-bit integer.
- There are no parentheses and no unary operators, the expression is always valid, and division by zero never occurs.
Examples
Input: ('0',)
Expected Output: 0
Explanation: Single one-character literal zero.
Input: ('2147483647',)
Expected Output: 2147483647
Explanation: Single literal at the literal bound 2^31 - 1.
Hints
- A literal can have several digits and spaces carry no meaning, so finish reading a whole number before applying the operator written before it.
- Because `*` and `/` bind tighter than `+` and `-`, a pending `+` or `-` cannot take full effect until every `*` and `/` that immediately follows it has been applied, in left-to-right order.
- Division must discard the fractional part (round toward zero); check what your language's integer division does if a value you divide can be negative.