Four-Function Calculator
MediumStack
Problem
Evaluate an arithmetic expression expr made of non-negative integers, the operators +, -, *, / and spaces. There are no parentheses. Multiplication and division bind tighter than addition and subtraction, and operators of equal precedence are applied left to right.
Integer division truncates toward zero. Return the result. Do not use any built-in expression evaluator.
Example 1
- Input:
- expr = "3 + 4*2 - 6/4"
- Output:
- 10
4·2 = 8 and 6/4 = 1, so 3 + 8 - 1 = 10.
Example 2
- Input:
- expr = " 20 / 3 * 3 "
- Output:
- 18
Left to right: 20/3 = 6, then 6·3 = 18.
Constraints
- 1 ≤ expr.length ≤ 3·10^5
- The expression is valid and never divides by zero
- All intermediate results fit in a 32-bit signed integer
Hint
Show the first hint
Additions and subtractions can be postponed; multiplications and divisions must be applied as soon as the right operand is known.
Walkthrough
How to approach it
01Clarify before coding
- Are there parentheses or unary minus? No.
- How does division round? Toward zero.
- Can numbers have several digits and spaces around them? Yes, both.
02Brute force
Tokenise, then repeatedly find the leftmost * or /, replace the three tokens by the result, and finally do the same for + and -.
Cost: Each replacement shifts the token list: O(n²) for 10^5 operators.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.