Basic Calculator

Problem

Given a string s representing an expression, implement a basic calculator to evaluate it.

Thought Process

• We have a sign variable that keeps track of the previous sign

Solution

class Solution:
    def calculate(self, s: str) -> int:
        sign = 1
        numbers = set("0123456789")
        stack = []
        sums = 0
        num = 0
        
        for i in range(len(s)):
            #getting the number
            #we don't want to apply the sign here
            if s[i] in numbers: 
                num = num*10 + int(s[i])
            elif s[i] == "+":
                sums = sums + num*sign
                num = 0
                sign = 1
            elif s[i] == "-":
                sums = sums + num*sign
                num = 0
                sign = -1
            elif s[i] == '(':
                stack.append(sums)
                stack.append(sign)
                sums = 0
                sign = 1
            elif s[i] == ')':
                sums = sums + num*sign
                sums*=stack.pop()
                sums += stack.pop()
                num = 0
            
            
        if num != 0:
            sums+=sign*num
                
                
        return sums
            
                

Time Complexity

• Time: O(n)

• Space: O(n)