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 eval built-in library function.

Difficulty: interview

Starter code:

class Solution:
    def calculate(self, s: str) -> int:
        

Solutions:
class Solution:
     def calculate(self, s):
         """
         :type s: str
         :rtype: int
         """
         res = 0
         num = 0
         sign = 1
         stk = []
 
         for c in s:
             if c.isdigit():
                 num = 10 * num + (ord(c) - ord('0'))
             elif c == '+':
                 res += sign * num
                 num = 0
                 sign = 1
             elif c == '-':
                 res += sign * num
                 num = 0
                 sign = -1
             elif c == '(':
                 stk.append(res)
                 stk.append(sign)
                 res = 0
                 sign = 1
             elif c == ')':
                 res += sign * num
                 res *= stk.pop()
                 res += stk.pop()
                 num = 0
                 sign = 1
 
         if num:
             res += sign * num
         return res

class Solution:
     def calculate(self, s):
         """
         :type s: str
         :rtype: int
         """
         total, tmp, sign = 0, 0, 1
         numStack = []
         signStack = []
         for c in s:
             if c == '+':
                 total, tmp, sign = total + tmp*sign, 0, 1
             elif c == '-':
                 total, tmp, sign = total + tmp*sign, 0, -1
             elif c == '(':
                 numStack.append(total)
                 signStack.append(sign)
                 total, tmp, sign = 0, 0, 1
             elif c == ')':
                 total += tmp * sign
                 total, tmp, sign = total * signStack.pop() + numStack.pop(), 0, 1
             elif '0' <= c <= '9':
                 tmp = tmp * 10 + ord(c) - ord('0')
             else:
                 continue
         return total + tmp * sign

class Solution:
     def calculate(self, s):
         """
         :type s: str
         :rtype: int
         """
         if not s:
             return 0
         
         res=0
         sign=1
         
         stack=[1]
         
         num=0
         
         for c in s:
             
             if c <='9' and c>='0':
                 num=num*10+ord(c)-ord('0')
                 #print(num)
             elif c in '+-':
                 res+=sign*num
                 #print(res)
                 if c=='+':
                    #print(stack)
                    sign=stack[-1]
                 else:
                    sign=stack[-1]*(-1)
                 num=0
             elif c=='(':
                 stack.append(sign)
             elif c==')':
                 stack.pop()
         #print('outsideloop',res)
         res+=sign*num
         
         return res

class Solution:
     def calculate(self, s):
         """
         :type s: str
         :rtype: int
         """
         stack = []
         res = 0
         sign = 1
         number = 0
         for i in range(len(s)):
             c = s[i]
             if c.isdigit():
                 number = number * 10 + int(c)
                 
             elif c == "+":
                 
                 res += number * sign
                 sign = 1
                 number = 0
             
             elif c == '-':
                 
                 res += number * sign
                 sign = -1
                 number = 0
             elif c == "(":
                 stack.append(res)
                 stack.append(sign)
                 res = 0
                 sign = 1
                 number = 0
             elif c == ')':
                 res += number * sign
                 res *= stack.pop()
                 res += stack.pop()
                 number = 0
                 sign = 1
         
         res += number * sign
                 
         
         return res

class Solution:
     def calculate(self, s):
         result = number = 0 
         sign = 1
         stack= []
         for i in s:
             if i == ' ':
                 continue
             if i.isdigit():
                 number = number * 10 + int(i)
             elif i == '+':
                 result += sign * number
                 number = 0 
                 sign = 1 
             elif i == '-':
                 result += sign * number 
                 number = 0 
                 sign = -1
             elif i == '(':
                 stack.append(result)
                 stack.append(sign)
                 result = 0 
                 number = 0 
                 sign = 1 
             elif i == ')':
                 result += sign * number 
                 number =  0
                 sign = 1 
                 #result += stack.pop() * stack.pop()
                 result = result * stack.pop() + stack.pop()
         result += number * sign
         return result 
                 


class Solution:
     def calculate(self, s):
         """
         :type s: str
         :rtype: int
         """
         sign=[1]
         nums=0
         total=0
         latestsign=1
         for c in s:
             
             if c.isdigit():
                 nums=10*nums+int(c)
             elif c=='(':
                 nums=0
                 sign.append(latestsign)
             elif c==')':
                 total=total+latestsign*nums
                 sign.pop()
                 nums=0
             elif c in ['+','-']:
                 total=total+latestsign*nums
                 latestsign=sign[-1]*(+1 if c=='+' else -1)
                 nums=0
         
         return total+latestsign*nums

class Solution:
     def calculate(self, s):
         """
         :type s: str
         :rtype: int
         """
         expression = s
         s = []
         res = 0
         curr = 0
         sign = 1
         for c in expression:
             # print(c,res)
             if c.isdigit():
                 curr *= 10
                 curr += int(c)
             if c == "+":
                 res += sign * curr
                 curr = 0
                 sign = 1
             if c == "-":
                 res += sign * curr
                 curr = 0
                 sign = -1
             if c == "(":
                 s.append(res)
                 s.append(sign)
                 sign = 1
                 res = 0
             if c == ")":
                 res += sign * curr
                 curr = 0
                 res *= s.pop()
                 res += s.pop()
         
         if curr != 0:
             res += sign * curr
         return res