Basic Calculator II
Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. You may assume that the given expression is always valid. Do not use the eval built-in parser.
Constraints:
- 1 <= s.length <= 3 * 10^5
- s consists of integers, '+', '-', '*', '/'
- s does not contain any spaces
Examples:
Input: 3+2*2
Output: 7
Explanation: First, we calculate the multiplication 2*2 = 4. Then we add 3 + 4 = 7.
Input: 3/2
Output: 1
Explanation: The division is truncated toward zero, so 3/2 = 1.
Input: 3+5 / 2
Output: 5
Explanation: First, we calculate the division 5/2 = 2. Then we add 3 + 2 = 5.
Solutions
Stack
We iterate through the string and whenever we encounter a digit, we update the current number. Whenever we encounter an operator, we calculate the result based on the current operator and the previous operator. We use a stack to store the intermediate results.
def calculate(s:
str) -> int:
stack, num, sign = [], 0, "+"; for i in s:
if i == ' ':
continue; if i.isdigit():
num = num * 10 + int(i); if i in '+-*/':
if sign == '+':
stack.append(num); elif sign == '-':
stack.append(-num); elif sign == '*':
stack.append(stack.pop() * num); elif sign == '/':
stack.append(int(stack.pop() / num)); sign, num = i, 0; if sign in '+-':
stack.append(num if sign == '+' else -num); return sum(stack)Follow-up:
How would you handle the case where the input string contains parentheses?
