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-negative integers and empty spaces .

解题方法

方法1

  • 先转换为reverse polish notation
  • 然后再stack的方法计算值

但是要记住如何转换为RPN

方法2

也利用了stack, 但是只需要loop through string的过程中计算值就可以

我们在遍历这个string的时候，除了space，只有5种可能，我们要根据他们分类讨论

  • 数字
  • +
  • -
  • (
  • )

括号内算作是另一个作用域，其实就是另一个式子，可以用递归（需要找到)），也可以用另一种方法在 不递归的情况下处理，那么当我们计算完括号内的值后，又需要得到括号之前的值来和 括号内的结果相加/减，所以我们要记录1. 之前的值， 2. 括号的正负，这种跟上一个 相邻的结构一般都是用stack。

现在我们明白遇到(就应该采取类似的方法计算，那么再考虑+, -, )就可以了

需要三个variable来keep track这个过程

  • result 当前作用域的结果，在括号内为一个单独的作用域
  • number 当前两个operator之间的数字
  • sign 当前的符号正负值

方法3

利用stack的方法，更简洁

Solution

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        length = len(s)
        stack = []
        result = 0
        number = 0
        sign = 1 # sign 表示的当前number之前的operator

        for i in range(length):
            if s[i].isdigit():
                # 当前的数字还在继续
                number = number * 10 + int(s[i])
            elif s[i] == "+":
                # 当前的数字结束了，应该将它加/减到结果中，然后继续往下
                result += sign * number
                number = 0
                sign = 1
            elif s[i] == "-":
                # 同"+"号
                result += sign * number
                number = 0
                sign = -1
            elif s[i] == "(":
                # 进入括号的作用域，stack保存之前的信息，并且更新result, sign,number
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
                # number = 0
                # number should already be 0, cause only + or - can precede (
            elif s[i] == ")":
                # 括号的作用域该退出了，得出括号内的结果
                # 并与之前保存的信息进行计算
                result += sign * number
                sign = stack.pop()
                result = sign * result + stack.pop()
                number = 0
        if number:
            result += sign * number
        return result

Reference