文章目录
- 题目描述
- 思路分析
- 完整代码
题目描述
给你一个字符串表达式 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
```