Basic Caculator

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, /, (, ) operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

思路：用stack, 一个存数，一个存operation。遇到符号，就检查上一个operation是不是*或者/是的话就先算。遇到反括号‘）’,就一直算到遇到‘（’为止。最后loop完s，nums中只剩数字，ops中只剩+ or -。一个一个op地pop出来，然后算好push回去就行了。

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: ints
        """
        num, nums, ops = 0, [0], []
        s = s + '#'

        for i in range(len(s)):
            if s[i] in '1234567890':    # if it is a number.
                num = num*10+int(s[i])
            else:                       # if it is not a number
                if i>0 and s[i-1] not in '+-*/()':
                    nums.append(num)
                    num = 0
                if s[i] in '+-*/':      # check if pre is */
                    if ops and (ops[-1] in '*/' or s[i] in '+-' and ops[-1] in '+-'): # if so we applyop
                        y, x, op = nums.pop(), nums.pop(), ops.pop()
                        nums.append(self.applyOp(x,y,op))
                    ops.append(s[i])
                elif s[i] in '(':       # heihei
                    ops.append(s[i])
                elif s[i] == ')':       # loop untill find '('
                    while ops and ops[-1]!='(':
                        y, x, op = nums.pop(), nums.pop(), ops.pop()
                        nums.append(self.applyOp(x,y,op))
                    ops.pop()

        while ops:  # construct final value
            y, x, op = nums.pop(), nums.pop(), ops.pop()
            nums.append(self.applyOp(x,y,op))
        return nums[-1]

    def applyOp(self, x, y, op):
        """
        opertion helper
        :type x: int
        :type y: int
        :type op: str
        :rtype: int
        """
        if op == '+':
            return x+y
        elif op == '-':
            return x-y
        elif op == '*':
            return x*y
        elif op == '/':
            if x//y<0 and x%y!=0:
                return x//y + 1
            else:
                return x//y

so = Solution()
ans = so.calculate('1-1+1')
print(ans)
ans = so.calculate('1+4*(2-3)+(4/2+1)')
print(ans)