给你一个字符串表达式
s ，请你实现一个基本计算器来计算并返回它的值。s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开。整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在
[-231, 231 - 1] 的范围内。注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如
eval() 。示例 1：
示例 2：
示例 3：
说明：
1 <= s.length <= 3 * 105
s表示一个 有效表达式
- 表达式中的所有整数都是非负整数，且在范围
[0, 231 - 1]内
- 题目数据保证答案是一个 32-bit 整数
解法一：栈 （推荐）
这道题的表达式没有括号，只有
+ - * /，所以只需要处理乘除优先级。加减的优先级最低，因此我们可以把整个表达式理解成：若干个“已经处理完乘除的加法项”之和。
比如：
3 + 2 * 2 可以看成 3 + 4 。我们用一个栈就可以处理优先级：加减直接作为加法项入栈；乘除立即和栈顶合并；最后栈求和。
也就是，
- 遇到
+或-，直接把当前数字作为正数或负数压栈，用栈保存这些“加法项”；
- 遇到
*或/，说明当前数字要先和栈顶的上一项结合，算完以后再把结果放回栈里。
- 最后，把栈里所有项求和，就是答案。
我们从左到右扫描字符串，维护三个变量：
sign 的含义非常重要。它不是当前字符，而是上一个运算符，也就是“应该如何处理刚刚读完的这个数字”。比如扫描到
3 + 2 * 2 当我们读完第一个
3，遇到 + 时，就根据之前的 sign = '+' 把 3 压栈。然后把 sign 更新成 +，表示下一个数字 2 前面的运算符是加号。当读完第二个
2，遇到 * 时，根据 sign = '+' 把 2 压栈。然后把 sign 更新成 *。最后读完第三个
2 时，根据 sign = '*'，把栈顶 2 弹出，与当前数字 2 相乘，得到 4 再压回栈。此时栈是
[3, 4]，求和得到 7。有两点注意：
- 结尾要额外处理
- 在循环里判断
i == len(s) - 1； - 给字符串末尾补一个
+，统一触发最后一个数字的处理。
表达式里的数字通常是在遇到下一个运算符时才被处理的。可是最后一个数字后面没有运算符。
有两种写法：
第二种逻辑更干净。
- 除法不能用
//
题目要求除法向
0 截断。比如：
5 / 2 -> 2，-5 / 2 -> -2，但 Python 的
// 是向下取整：-5 // 2 == -3 ，所以这里不能直接用 //。更简单的写法是
int(prev / num)，它会向 0 截断，符合题目要求。复杂度分析
- 时间复杂度：
O(n)，其中n是字符串长度。我们只扫描一遍表达式。
- 空间复杂度：
O(n)。最坏情况下表达式全是加减，例如：1+2-3+4-5
每个数字都会作为一个独立加法项进入栈。
解法二：常数空间优化 （最优解）
栈写法最后会做
sum(stack) ，但其实我们不一定要把所有加法项都存下来。栈的作用：
- 对于
+和 ，旧的上一项已经确定，不会再被乘除修改；
- 对于 和
/，只会影响最近的那一项，也就是栈顶。
所以我们可以不用栈，而是维护两个变量：
当遇到
+ 或 - 时，说明前一个 lastNumber 已经彻底结束，可以加入 res。然后当前数字成为新的 lastNumber。当遇到
* 或 / 时，不能动 res，只需要更新 lastNumber：最后返回
res + lastNumberWalk Through Example
以
3 + 2 * 2为例：先读到
3，后面遇到 +，此时 lastNumber = 3。当进入 + 逻辑时，把旧的 lastNumber 加入 res，于是 res = 3，新的 lastNumber = 2。接着遇到
*，2 还不能加入 res，因为后面要乘。读到最后一个 2 后，执行乘法 lastNumber = 2 * 2 = 4 ，最终返回 res + lastNumber = 3 + 4 = 7 。复杂度分析
- 时间复杂度：
O(n)，仍然只扫描一次字符串。
- 空间复杂度：
O(1)，只使用常数个变量。
总结
这题没有括号，所以主要问题是处理乘除优先级。
这两种解法本质上是同一个思路。
- 栈版本把表达式转换成一堆加法项：
3 + 2 * 2 - 4 / 2，会被处理成[3, 4, -2]，最后求和。
- 常数空间版本则不保存完整列表，而是把已经确定的项提前加入
res，只保留最后一个还可能被乘除影响的项lastNumber。
可以这样理解：
- 栈：保存所有加法项，最后 sum。
- 常数空间：已确定的项直接加到 res，只保留最后一项。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-227-基础计算器-ii
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 208] 实现 Trie
下一篇
[Leetcode 236] 二叉树的最近公共祖先