A calculator app lets people type a whole sum at once, brackets and all, and should give the answer a school calculator would.
Write calculate(expr: str) -> int that evaluates expr.
exprholds non-negative integers, the operators+,-,*and/, the brackets(and), and spaces. Spaces can appear anywhere between tokens, but never inside a number.- A bracketed part is worked out first. Then
*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:7 / 2is 3 and-7 / 2is -3, not -4.- A
-is a unary minus (it flips the sign of what comes right after it) when it is the first token, comes right after(, or comes right after another operator, including another unary minus. So-3,-(2 + 1),4 * -2,1 - -1and--3are all valid. Every other-is subtraction. There is no unary plus. - This is the full version of Basic Calculator II, which has no brackets and no unary minus.
The expression is always valid and never divides by zero. Every number, every intermediate result and the answer fit in a signed 64-bit integer.
calculate("1 + 2 * 3") # 7
calculate("(1 + 2) * 3") # 9
calculate("-(4 - 10) / 4") # 1 (-(-6) is 6, and 6 / 4 truncates to 1)
calculate("7 - -2 * 3") # 13 (-2 * 3 is -6, and 7 - (-6) is 13)
calculate("-7 / 2") # -3 (-3.5 truncated toward zero)
calculate(" 2*(5-(3+ 4)) ") # -4
Constraints: 1 <= len(expr) <= 3 * 10^5. Brackets can nest up to 10^5 levels deep, and up to 10^5 unary minuses can stand in a row, so don't recurse once per level: Python's default limit is about 1,000 calls deep, and the tests go much deeper.
⭐ Bonus: a speed test on about 300,000 characters earns a star in O(n).
Show hint
treat a bracket like a fresh, smaller expression. When you meet (, save what the current level was in the middle of (its finished terms, the operator in front, a waiting unary minus) on a stack and start empty. At ), add up the inner level's terms, restore the saved level, and use the sum as if it were a number.