Description
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces ``.
Example 1:
Input: "1 + 1"
Output: 2
Example 2:
Input: " 2-1 + 2 "
Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
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:
res, val, sign, stack = 0, 0, 1, []
for ch in s:
if ch.isdigit():
val = 10 * val + int(ch)
elif ch in '-+':
res += sign * val
val = 0
sign =[-1, 1][ch == '+']
elif ch == '(':
stack.append(res)
stack.append(sign)
sign, res = 1, 0
elif ch == ')':
res += sign * val
res *= stack.pop()
res += stack.pop()
val = 0
return res + val * sign
# 37/37 cases passed (72 ms)
# Your runtime beats 92.26 % of python3 submissions
# Your memory usage beats 7.14 % of python3 submissions (14.2 MB)
2. Recursion
# Time: O(n)
# Space: O(n)
class Solution:
def calculate(self, s: str) -> int:
arr = []
for c in s:
arr.append(c)
return self.helper(arr)
def helper(self, arr):
stack = []
sign = '+'
num = 0
while len(arr) > 0:
c = arr.pop(0)
if c.isdigit():
num = num*10 + int(c)
if c == '(':
num = self.helper(arr)
if c == '+' or c == '-' or c == ')' or len(arr) == 0:
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
sign = c
num = 0
if c == ')':
break
return sum(stack)
# 37/37 cases passed (4300 ms)
# Your runtime beats 5.1 % of python3 submissions
# Your memory usage beats 7.14 % of python3 submissions (16.4 MB)