Basic Calculator

题目

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open(and closing parentheses), the plus+or minus sign-,non-negativeintegers and empty spaces.

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note:Do not use theevalbuilt-in library function.

思路分析

这道题的input string中是有括号的，有括号在运算的时候就会有先后，联想到数据结构就会想到stack可以很好地帮助带括号的运算表达式。在整个实现过程中，边界问题是容易忽视，另外每一次遇到 '(' 时就要重新把sign位置为1

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        sLen = len(s)
        index, sign = 0, 1
        while index < sLen:
            if s[index].isdigit():
                tmp = index
                while index < sLen and s[index].isdigit(): index += 1   <<<<<<注意边界
                stack.append(sign * int(s[tmp: index]))
                index -= 1
            elif s[index] == "+": sign = 1
            elif s[index] == "-": sign = -1
            elif s[index] == "(": 
                stack.append(sign)
                stack.append('(')
                sign = 1              >>>>>> 遇到'('时，sign位要重新置为1
            elif s[index] == ")":
                result = stack.pop()
                while stack[-1] != "(": result += stack.pop()
                stack.pop()
                stack.append(stack.pop() * result)
            index += 1
        if not stack: return result
        result = 0
        while stack: result += stack.pop()
        return result