440. Desk Calculator
A desk calculator receives a line such as "18 / 4 * 3 - 2 * 5". It holds whole numbers, the four operators +, -, *, / and spaces, but no brackets. Multiplication and division bind tighter than addition and subtraction, and operators of equal strength are applied from left to right. A number may carry one leading minus sign, as in 6 * -3 or -8 / 3.
Return the value of expression. Integer division discards the fractional part and rounds toward zero, so -8 divided by 3 is -2. The expression is always valid and never divides by zero. Every number, every partial product or quotient, and the final result fits in a signed 32-bit integer. The line can have up to 30,000 characters, so the work must be linear in its length.
Example 1
- Input:
- expression = " 40 / 6 * 3 - 2 * -4 + 9"
- Output:
- 35
- Explanation:
40 / 6 is 6, times 3 gives 18. Then 2 * -4 is -8 and 18 - (-8) = 26. Adding 9 gives 35.
Example 2
- Input:
- expression = "-25/4+7*3-10"
- Output:
- 5
- Explanation:
-25 / 4 truncates toward zero to -6. Then 7 * 3 = 21, so the total is -6 + 21 - 10 = 5.
Constraints
1 ≤ expression.length ≤ 3 * 104
The characters are digits, +, -, *, / and spaces.
The expression is valid; division never has a zero divisor.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)