A shop's till lets staff type quick sums like 3 + 2 * 4 and should give the same answer a school calculator would. There are no parentheses.
Write calculate(expr: str) -> int that evaluates expr.
exprholds non-negative integers, the operators+,-,*and/, and spaces. Spaces can appear anywhere between tokens, but never inside a number.*and/come before+and-. Operators of the same kind go left to right:8 / 4 * 2is(8 / 4) * 2 = 4./is integer division that truncates toward zero.- There is no unary minus: every
-sits between two numbers. The expression is always valid, never divides by zero, and the answer and every partial result fit in a signed 32-bit integer.
calculate("3 + 2 * 4") # 11
calculate(" 20 / 6 - 1 ") # 2 (20 / 6 = 3.33, truncated to 3)
calculate("7 - 9 / 2 * 3") # -5 (9 / 2 = 4, then 4 * 3 = 12, and 7 - 12)
calculate("8*3/5+0") # 4 (24 / 5 = 4.8, truncated)
calculate("42") # 42
Constraints: 1 <= len(expr) <= 3 * 10^5; numbers are at most 2^31 - 1.
⭐ Bonus: repeatedly finding the next operator to apply and splicing its result back into the string is O(n²) and still passes; a speed test on 3 * 10^5 characters earns a star in O(n).
Show hint
a + or - can't be applied yet, because a * or / might follow and grab its right-hand number. Keep the finished terms on a stack, and let * and / update the top one.