难度: Hard
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 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 * 105s 由数字、'+'、'-'、'('、')'、和 ' ' 组成s 表示一个有效的表达式"+(2 + 3)" 无效)"-(2 + 3)" 是有效的)运行时间: 32 ms
内存: 17.3 MB
class Solution:
def calculate(self, s: str) -> int:
i, curNum, curOp, stack = 0, 0, 1, []
while i < len(s):
if s[i] == '+':
curOp = 1
elif s[i] == '-':
curOp = -1
elif s[i] == '(':
stack.append((curNum, curOp))
curNum, curOp = 0, 1
elif s[i] == ')':
ops = stack.pop()
curNum = ops[0]+ops[1]*curNum
elif s[i] != ' ':
k = 0
while i < len(s) and s[i] not in ' +-)':
k = k*10+int(s[i])
i += 1
curNum = curNum+curOp*k
continue
i += 1
return curNum
该题解使用了一个栈来处理带括号的表达式。首先，通过一个循环遍历整个字符串，使用变量curNum来维护当前的数字，使用curOp来表示当前的操作符（加号为1，减号为-1）。当遇到'('时，将当前的curNum和curOp存入栈中，并重置curNum和curOp，这样可以处理新的子表达式。当遇到')'时，将栈顶的元素（之前的curNum和curOp）取出，根据这些值计算括号内表达式的值。对于数字的处理，使用while循环连续读取字符直到非数字，计算出完整的数字并根据之前的curOp更新curNum。最终，在字符串遍历完成后，curNum将包含整个表达式的计算结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def calculate(self, s: str) -> int:
i, curNum, curOp, stack = 0, 0, 1, []
while i < len(s):
if s[i] == '+':
curOp = 1 # 设置当前操作为加法
elif s[i] == '-':
curOp = -1 # 设置当前操作为减法
elif s[i] == '(': # 遇到左括号，将当前状态入栈
stack.append((curNum, curOp))
curNum, curOp = 0, 1 # 重置当前数和操作为默认状态
elif s[i] == ')': # 遇到右括号，计算括号内表达式的值
ops = stack.pop()
curNum = ops[0] + ops[1] * curNum
elif s[i] != ' ': # 处理数字
k = 0
while i < len(s) and s[i] not in ' +-)':
k = k * 10 + int(s[i])
i += 1
curNum = curNum + curOp * k # 根据当前操作更新curNum
continue # 因为i在内部循环中已更新，跳过外层循环的i增加
i += 1 # 移动到下一个字符
return curNum # 返回计算结果
在题解中，为了正确处理和转换连续的数字字符为整数，使用了一个内部的循环。当遇到一个数字字符时，初始化一个变量 `k` 为 0，然后进入一个内部循环，这个循环会持续读取字符串中的连续数字字符。在每次循环中，将 `k` 的值乘以 10（这是因为我们正在处理十进制数，并且每向前一位，数值的大小就放大10倍），然后将当前字符表示的整数加到 `k` 上。这样，通过连续读取和更新 `k` 的值，就能将一串连续的数字字符正确地转换为整数。
在遇到左括号 '(' 时，意味着将要开始一个新的子表达式的计算。此时将当前的 `curNum`（当前已经计算的结果）和 `curOp`（最近的操作符）压入栈，是为了保存当前表达式的上下文状态，以便在后续遇到对应的右括号 ')' 时能恢复这个状态继续之前的计算。重置 `curNum` 和 `curOp` 则是因为括号内的表达式应当独立计算，它们的计算结果最终会根据之前保存的状态（操作符和数值）与外部表达式合并。因此，重置这两个变量可以确保不会将外部的计算结果错误地混入新的子表达式中。
当遇到右括号 ')' 时，首先从栈中弹出之前压入的元素，这些元素包括上一个未完的表达式的累计结果 `prevNum` 和与之对应的操作符 `prevOp`。这时，栈顶的 `prevNum` 表示在当前括号表达式之前已经计算的结果，而 `prevOp` 表示这个括号表达式外的操作符，即这个括号表达式应该如何影响整体计算结果（是加上还是减去括号内的结果）。括号内的表达式的计算结果已经在 `curNum` 中。因此，通过执行 `prevNum + prevOp * curNum` 计算，可以将括号内的结果合并到总表达式的计算中。这样，括号表达式的计算结果被正确地加入到了整体的计算流程中。