面试题-基本计算器I

题目来源：https://leetcode-cn.com/problems/basic-calculator/

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格。

示例 3:

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

建立这样一个计算器，可以借助栈来实现。注意到加法满足交换律，而减法不满足交换律，所以把减法看作是下一个数字的符号。如3 -4 =3+（-4），这样每个数字就由一个标识sign来表示其正负性。

注意每次设置的sign都是暂存当前的操作符，这个sign会等到下一个数字来时才使用。比如3-4，读取到-号时，由于num为3，所以ans = ans + sign*num = 0 + 1*3= 3，然后暂存-号，置sign=-1，num=0，下一个数字4来到时，num=4，此时输入全部读取完毕，返回ans+sign*num = 3+（-1）*4 = -1。可以看到每次运算时用的sign都是前一个时刻存储的。

对于字符串中的每个字符：

如果是数字，将其值存入num。另外，注意到形如"123"的字符串，每次读下一个字符时，对上一个读入的值都应该乘10。
如果是+，sign*num加入ans，将sign置1，num清零。
如果是-，sign*num加入ans，将sign置-1，num清零。
如果是(，将当前结果ans和sign入栈，sign置1，ans清零。
如果是)，sign*num加入ans（此时ans在前面清零过），再从栈中先取出sign，sign*ans，然后取出前面暂存的ans，加上当前结果ans += sign*ans

最后返回ans + sign*num。（几种情况：输入为纯数字 / 输入有括号 / 输入无括号）

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        num = 0
        ans = 0
        sign = 1
        stack = []

        for c in s:
            if c.isnumeric():
                num = num * 10 + int(c)
            elif c == '+':
                ans += sign * num
                sign = 1
                num = 0
            elif c == '-':
                ans += sign * num
                sign = -1
                num = 0
            elif c == '(':
                stack.append(ans)
                stack.append(sign)
                sign = 1
                ans = 0
            elif c == ')':
                ans += sign * num
                ans *= stack.pop()
                ans += stack.pop()
                num = 0
        return ans + sign * num

参考：

https://leetcode-cn.com/problems/basic-calculator/solution/ji-ben-ji-suan-qi-by-leetcode/