Given a string s holding a valid expression with non-negative integers, the operators +, -, *, / and spaces, evaluate it and return the integer result. Multiplication and division bind tighter than addition and subtraction, and division truncates toward zero. There are no parentheses, and you may not use built-in expression evaluators such as eval().
2*2 is done first, then 3 + 4.5 / 2 = 2, then 3 + 2.- 1 <= s.length <= 3 * 10^5
- All numbers are in [0, 2^31 - 1]
- The answer and every intermediate value fit in a 32-bit integer
- The expression is valid
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force could do two passes, first finding and evaluating every * and / and rebuilding the string, then adding and subtracting what is left. That rescans and rebuilds strings repeatedly. The cleaner view is that the expression is a sum of signed terms. Keep the previous operator: when a number is complete, + and - start a new term on the stack, while * and / apply immediately to the latest term, which is exactly where higher precedence belongs. Summing the stack at the end gives the answer. You can even replace the stack with two variables.
Algorithm
- Set
num = 0,op = "+"and an empty stack. - Read characters; build multi-digit numbers with
num = num * 10 + digit, skipping spaces. - When you reach an operator or the end: apply
optonum(pushnum, push-num, multiply the top, or divide the top truncating toward zero). - Set
opto the current operator and resetnum = 0. - Return the sum of the stack.
O(n)Space: O(n), or O(1) with a running total and a last-term variablei is the last index, even if that character is a digit. In Python, truncate toward zero with int(a / b) or sign handling, because -3 // 2 is -2, not -1.class Solution: def calculate(self, s: str) -> int: stack = [] # signed terms num, op = 0, '+' # op is the operator before num n = len(s) for i, c in enumerate(s): if c.isdigit(): num = num * 10 + int(c) # Apply the previous operator at an operator or at the last character. if (not c.isdigit() and c != ' ') or i == n - 1: if op == '+': stack.append(num) elif op == '-': stack.append(-num) elif op == '*': stack.append(stack.pop() * num) else: top = stack.pop() q = abs(top) // num # truncate toward zero stack.append(q if top >= 0 else -q) op, num = c, 0 return sum(stack)