[224][困难][栈] 基本计算器

题目描述

224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

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

提示：

• 1 <= s.length <= 3 * 105

• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成

• s 表示一个有效的表达式

解题思路

只有加减号的运算, 不需要考虑运算符的优先级, 只需要从左到右逐个计算就可以.

在遇到括号时, 需要优先计算括号中的表达式, 因此需要将前面计算的结果和符号缓存起来, 计算得到括号内子表达式的值之后, 再与之前结果和符号计算得到新结果.

由于括号是可以嵌套的, 应对这种情况需要使用递归的方式处理, 因此使用栈的方式缓存之前计算的结果和符号.

计算器题目的一个关键点是在何时触发计算. 计算都是在将一个完整的数字获取到之后, 才能与之前和数字和计算符号一起计算. 因此问题就转变成了如何判断数字结束. 本题中有以下几种情况:

• 遇到了+, -计算符

• 遇到右括号)

• 遇到字符串结束

遇到这些情况就要发生计算, 并维护好计算后的重置. 遇到其他符号无需计算, 只需要更新当前数字, 或者压栈.

首先设定:

• res: 表示左边表达式除去栈内保存元素的计算结果

• pre_sign: 表示当前数字之前的运算符

• num 表示当前遇到的数字

• 用栈保存遇到左括号时前面计算好了的结果和运算符

过程为:

• 如果当前是数字，那么更新计算当前数字

• 如果当前是操作符+或者-，那么需要更新计算当前计算的结果 res，并把当前数字 num 设为 0，pre_sign 设为正负，重新开始

• 如果当前是 ( ，那么说明遇到了右边的表达式，而后面的小括号里的内容需要优先计算，所以要把 res, pre_sign 进栈，更新 res 和 pre_sign 为新的开始

• 如果当前是 ) ，那么说明右边的表达式结束，即当前括号里的内容已经计算完毕，所以要把之前的结果出栈，然后计算整个式子的结果

• 最后，当所有数字结束的时候，需要把最后的一个 num 也更新到 res 中

class Solution:
    def calculate(self, s: str) -> int:
        res = 0
        num, pre_sign = 0, 1
        stack = []

        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c in ('+', '-'):
                res += pre_sign * num
                num, pre_sign = 0, 1 if c == '+' else -1
            elif c == '(':
                stack.append(res)
                stack.append(pre_sign)
                res, pre_sign = 0, 1
            elif c == ')':
                res += pre_sign * num
                res *= stack.pop()
                res += stack.pop()
                num = 0
        res += pre_sign * num
        return res

参考资料

• 如何想到用「栈」？思路来自于递归