a Python solution


  • 0
    A
    class Solution(object):
        def char_type(self, c):
            if c == '+' or c == '-' or c == '*' or c == '/':
                return 'op'
            elif c == ' ':
                return 'sp'
            else:
                return 'num'
        
        def operate(self, op, num_stack):
            nr = num_stack.pop()
            nl = num_stack.pop()
            if op == '+':
                num_stack.append(nl + nr)
            elif op == '-':
                num_stack.append(nl - nr)
            elif op == '*':
                num_stack.append(nl * nr)
            elif op == '/':
                num_stack.append(nl / nr)
        
        def calculate(self, s):
            """
            :type s: str
            :rtype: int
            """
            precedence = {'+':1,'-':1,'*':2,'/':2}
            num_stack = []
            op_stack = []
            i = 0
            while i < len(s):
                c = s[i]
                ct = self.char_type(c)
                if ct == 'num':
                    num = int(c)
                    while i+1 < len(s) and self.char_type(s[i+1]) == 'num':
                        num = num*10 + int(s[i+1])
                        i = i + 1
                    num_stack.append(num)
                elif ct == 'op':
                    while len(op_stack)>0 and precedence[c] <= precedence[op_stack[-1]]:
                        op = op_stack.pop()
                        self.operate(op, num_stack)
                    op_stack.append(c)
                i = i + 1
            while len(op_stack) > 0:
                self.operate(op_stack.pop(), num_stack)
            return num_stack.pop()
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.