Basic Calculator II

Problem

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

(The difference between this and Basic Calculator I is that in here we have all the operands and no paranthese, while in Basic Calculator I we only had '+' and '-' and parantheses.)

Thought Process

• Multiplication and division need to be handled before addition and subtraction

• Once again here we are saving the previous sign like in Basic Calculator I

Solution

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        numbers = set("0123456789")
        num = 0
        operands = "*+-/"
        sign = '+'
        
        for i in range(len(s)):
            if s[i] in numbers:
                num = 10*num + int(s[i])
            
            if s[i] in operands or i == len(s)-1:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    num*=-1
                    stack.append(num)
                elif sign == '*':
                    prev = stack.pop()
                    stack.append(prev*num)
                elif sign == '/':
                    prev = stack.pop()
                    stack.append(int(prev/num))
                num = 0
                sign = s[i]
        
        return sum(stack)
                    

Time Complexity

• Time: O(n)

• Space: O(n)