题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个字符串，串内是一个有加减法和小括号的数学表达式，请计算表达式的结果。

思路分享

  • 最简的表达式为 a +/- b，即左部、符号、右部。加入小括号后，小括号内可以优先计算，化为一个数，也就是可当作左部或者右部。

  • 那么从左向右遍历字符串，只要记录已经计算后的结果、正在遍历的数字以及正在使用的计算符号就行。一旦遇到下一个符号，就把上一个符号和数字计算并加入到结果当中。遇到小括号，就把结果和符号保存到栈中，计算完小括号后，把值放右部，提取栈值和符号作为左部计算。

    https://leetcode.cn/problems/basic-calculator/solutions/646800/ru-he-xiang-dao-yong-zhan-si-lu-lai-zi-y-gpca/

代码解答（强烈建议自行解答后再看）

  • 参考题解
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
class Solution:
    def calculate(self, s: str) -> int:
        res, num, sign = 0, 0, 1 # 分别是结果，正在处理的数字，以及对应符号
        stk = list() # 作为存储括号内数值和符号的栈，两两一组
        for c in s:
            if c.isdigit():
                # 记录当前数字
                num *= 10
                num += int(c)
            elif c == '+' or c == '-':
                # 遇到符号，也就是说上一阶段的计算得结束了
                res += sign * num # 用 sign 就免除了再判断 + -
                num = 0
                sign = 1 if c == '+' else -1
            elif c == '(':
                # 保存当前结果，准备下一阶段的计算
                stk.append(res)
                stk.append(sign)
                res, sign = 0, 1
            elif c == ')':
                # 把栈的结果（上一层）与现有的结果合并
                res += sign * num
                num = 0
                res *= stk.pop() # 这里的 res 实际上是括号内部（或者说计算式的右侧）
                res += stk.pop() # 上一层的计算结果
        res += sign * num
        return res