Description
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces ``. The integer division should truncate toward zero.
Example 1:
Input: "3+2*2"
Output: 7
Example 2:
Input: " 3/2 "
Output: 1
Example 3:
Input: " 3+5 / 2 "
Output: 5
Note:
- You may assume that the given expression is always valid.
- Do not use the
evalbuilt-in library function.
Solutions
1. Stack
# Time: O(n)
# Space: O(n)
class Solution:
def calculate(self, s: str) -> int:
stack = []
res = 0
sign = '+'
val = 0
for i, ch in enumerate(s):
if ch.isdigit():
val = val * 10 + int(ch)
if (not ch.isdigit() and ch != ' ') or len(s) - 1== i:
if sign == '+':
stack.append(val)
elif sign == '-':
stack.append(-val)
elif sign == '/':
if stack[-1] > 0:
stack.append(stack.pop() // val)
else:
stack.append(int(stack.pop() / val))
elif sign == '*':
stack.append(stack.pop() * val)
sign = ch
val = 0
for num in stack:
res += num
return res
# 109/109 cases passed (96 ms)
# Your runtime beats 62.52 % of python3 submissions
# Your memory usage beats 88.89 % of python3 submissions (14.4 MB)