Basic Calculator II

题目

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.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note:Do not use theevalbuilt-in library function.

思路分析

这道题跟basic calculator思路很类似，都是使用stack的数据结构来实现，这道题目中没有括号，但是多了* 和／两种操作符。有了* 和／两种操作符，就要考虑优先级的问题了。整体 来讲是要从左到右进行操作，具体为：

• 先得到一个当前的数字
• 如果遇到+或-号，就带着符号apply到数字上
• 如果遇到*或／符号，就把stack中的最后一个数字与当前的这个数字进行*或／

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        index, result, sign = 0, 0, 1
        sLen = len(s)
        sign = '+'
        while index < sLen:
            if s[index].isdigit():
                tmp = index
                while index < sLen and s[index].isdigit(): index += 1
                num = int(s[tmp: index])
                index -= 1
            if (not s[index].isdigit() and s[index]!=' ') or index == sLen-1:
                if sign == '+': stack.append(num)
                elif sign == '-': stack.append(-num)
                elif sign == '*': stack.append(stack.pop() * num)
                elif sign == '/': 
                    tmp = stack.pop()
                    if tmp < 0 and tmp % num: stack.append(tmp/num + 1)  >>>>>
                    else: stack.append(tmp/num)
                sign = s[index]
            index += 1
        while stack: result += stack.pop()
        return result