227. Basic Calculator II

# Medium

key idea: stack

Search the operator then number

1) if the operator is "+", push the number to the stack;

2) if the operator is "-", push the opposite number to the stack;

3) if the operator is "*", pop the top number out to do calculate, then push back;

4) if the operator is "/", pop the top number out to do calculate, then push back. In python, "//" must distinguish negative and positive number.

Python

class Solution:
    def calculate(self, s: str) -> int:
        res = []
        i = 0
        (num, i) = self.findNumber(s, i)
        res.append(num)
        
        while i < len(s):
            # operators
            (operator, i) = self.findOperator(s, i)
            (num, i) = self.findNumber(s, i+1)
            if operator == "+":
                res.append(num)
            elif operator == "-":
                res.append(num*(-1))
            elif operator == "*":
                tmp = res.pop()
                res.append(tmp*num)
                print(res)
            else:
                tmp = res.pop()
                if tmp < 0:
                    res.append((abs(tmp)//num)*(-1))
                else:
                    res.append(tmp//num)
        # add all elements
        result = 0
        for x in res:
            result += x
        return result
    
    # find the first number from index of i
    def findNumber(self, s, i): 
        digits = "0123456789"
        num = 0
        while i < len(s):
            if s[i] in digits:
                num = 10*num + int(s[i])
                i += 1
            elif s[i] == " ":
                i += 1
                continue
            else:
                break
        return (num, i)  # index of next element after the number
    
    def findOperator(self, s, i):
        operators = "+-*/"
        while i < len(s):
            if s[i] in operators:
                break
            i += 1 
        return (s[i], i) # index of this operator

Python-2

class Solution:
    def calculate(self, s: str) -> int:
        # edge case
        if len(s) == 0:
            return 0
        
        # regular case
        preOperation = "+"
        num = 0
        lastNum = 0
        res = 0
        for i in range(len(s)):
            if s[i].isdigit():
                num = num*10 + int(s[i])
            if (s[i].isdigit() == False and s[i] != " ") or i == len(s) - 1:
                if preOperation == "+":
                    res += lastNum
                    lastNum = num
                elif preOperation == "-":
                    res += lastNum
                    lastNum = -num
                elif preOperation == "*":
                    lastNum *= num
                elif preOperation == "/":
                    lastNum = int(lastNum/num)
                preOperation = s[i]
                num = 0
        
        res += lastNum
        return res

In Python, 1//-10 = -1, because Python is "floor division", but the result we want is 0, so we can do int(1/-10) = 0