编写一个基本计算器

题目

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

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

示例 1:

输入: "1 + 1"
输出: 2

示例 2:

输入: " 2-1 + 2 "
输出: 3

示例 3:

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

说明：

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

解题思路

自己的思路是：先分割字符串，然后对于没有括号的部分，计算出来。碰到括号后，对括号内的部分，计算出来。然后再一起计算。这样的话，如果碰到较长的表达式，会出现爆栈的问题。

看了题解的思路，题解的思路太妙了……把每个+和-都作为数字的自带符号，然后全部相加。
如果碰到左括号，则把前面计算出来的结果、这个左括号前面的符号入栈，然后从头开始计算括号内的结果
如果碰到右括号，则把当前的结果和栈里的结果合并。合并的时候注意，1 - (4)，应该是括号内的结果，和括号前的符号（这里的-）相乘，然后再和1相加。（用到了加法的交换律，-4 + 1 = 1 + (-4)）

代码

官方题解版：

class Solution:
    def calculate(self, s: str) -> int:
        res, op = 0, 0
        sign = 1
        stack = []
        for ch in s:
            if ch.isdecimal():
                op = op * 10 + int(ch)
            elif ch == '+':
                res += sign * op
                sign = 1
                op = 0
            elif ch == '-':
                res += sign * op
                sign = -1
                op = 0
            elif ch == '(':
                stack += [res, sign]
                res, op = 0, 0
                sign = 1
            elif ch == ')':
                res += sign * op
                res *= stack.pop()
                res += stack.pop()
                op = 0
                sign = 1
        res += sign * op
        return res

本文地址：https://blog.csdn.net/sinat_41679123/article/details/107450439