leetcode(力扣) 224. 基本计算器（清晰思路，完整模拟）_实现一个简易版计算器leetcode

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：
输入：s = “1 + 1”
输出：2

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

示例 3：
输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

思路分析

模拟！开始！

例子：s = “(1+(4+5+2)-3)+(6+8)”

先设几个变量，别问为什么，先记就行。

1.变量res，记录当前括号里的内容总和。比如(4+5+2) 那总和就是res=11
2.变量num，记录当前整体数字，因为要遍历s，所以如果有152+1 这种，那么遍历的指针就应该是1，5，2，+，1。 然而152是一个数字整体，所以需要有一个num变量来应对这种情况。
3.变量sign，一个符号变量，1表示为加号，-1表示为减号。
4.变量stack。是个栈，存什么后面再说。

操作的步骤是：

• 如果当前是数字，那么更新计算当前数字；
• 如果当前是操作符+或者-，那么需要更新计算当前计算的结果 res，并把当前数字 num 设为 0，sign 设为正负，重新开始；
• 如果当前是 ( ，那么说明遇到了右边的表达式，而后面的小括号里的内容需要优先计算，所以要把 res，sign 进栈，更新 res 和 sign 为新的开始；
• 如果当前是 ) ，那么说明右边的表达式结束，即当前括号里的内容已经计算完毕，所以要把之前的结果出栈，然后计算整个式子的结果；
  最后，当所有数字结束的时候，需要把最后的一个 num 也更新到 res 中。

模拟过程：

例子：s = “(1+(4+5+2)-3)+(6+8)”

初始化:

res = 0
sign = 1
num = 0

其实这个初始化方法，可以理解成 s = 0+(1+(4+5+2)-3)+(6+8)，在最前面多了一个0+

• 遍历，当前字符为 ‘(’，直接将当前的res和sign进栈。然后重置res=0和sign=1。这里其实可以理解为，遇到 ‘(’ 说明发现了一个更深层的嵌套，此时将该深层嵌套外的值res和其符号sign都记录到栈里，然后重置了他俩，继续算更深层的括号。
• 继续遍历遇到字符 ‘1’ ，没的说直接计算当前累计值num，也就是num = 10 * num + 当前值。
• 继续遍历遇到字符 ‘+’ ，此时遇到加号说明num已经完整记录了当前数字(比如159，num已经等于159了，而不是1或者15)。计算当前的累计值res+=sign*num。这个没啥好说的 当前完整字符num乘以符号。
• 继续遍历遇到字符 ‘(’，同样，res和sign进栈，然后重置res和sign。
• 继续遍历遇到字符 ‘4’ ，计算num = 4
• 继续遍历到字符 ‘+’，计算当前res = 4，重置num和sign。
• 继续遍历到。。。直到第一个 ‘)’ ，说明当前括号已经算完，先算出来当前括号内的res，然后重置num，然后计算当前res和栈内保存的之前的数值(左边表达式的值)。比如在遍历到该 ‘)’ 时的stack = [0,‘1’,1,‘1’],这里解释一下，stack里的第一个值和第二个值就是我们初始化的res和sign。也就是s = 0+(1+(4+5+2)-3)+(6+8)，最前面扩充出来的0和+。stack里第二个值和第三个值就是在s = (1+(4+5+2)-3)+(6+8)遇到第二个 “(” 时候记录的他之前计算的值以及符号，显然是1和正号。当遇到右括号时，此时res就是(4+5+2)=11。符号sign为1。所以有 res *= stack.pop(),res += stack.pop()

完整代码

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        res = 0 # 记录当前括号内的总值
        num = 0 # 记录当前值的整体(比如156这种多位数)

        sign = 1  # 记录符号  1为正好， -1 为负号
        
        for c in s:
            if c.isdigit(): # 为数字的情况
                num = num*10 + int(c)
            
            elif c in '+-': # 正负号的情况
                res+= sign* num

                num = 0
                sign = 1 if c =='+' else -1
            elif c =='(': # 左括号的情况，进入了一个新的更深的嵌套
                stack.append(res)
                stack.append(sign)
                res = 0
                sign = 1
            elif c == ')': # 退出了当前嵌套
                res +=sign*num
                res *=stack.pop()
                res +=stack.pop()
                num = 0
        res += num* sign 
        return res
        ```

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31