实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符
+、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足
[-231, 231 - 1] 。注意：你不能使用任何将字符串作为表达式求值的内置函数，比如
eval() 。示例 1：
示例 2：
示例 3：
说明：
1 <= s <= 104
s由整数、'+'、'-'、'*'、'/'、'('和')'组成
s是一个 有效的 表达式
这题 相比 Basic Calculator II，多了括号。
括号的本质是：括号内部是一个独立表达式，它应该先被计算成一个整数，再作为外层表达式里的一个普通数字继续参与运算。
因此这题需要同时处理 运算符优先级 和 括号作用域。
所以有两个自然方向：
- 用 双栈 全局模拟表达式求值；
- 用 递归 把每个括号表达式当成子问题求值。
解法一：双栈
双栈是最通用的表达式求值模型。
我们维护两个栈 - 一个数字栈
nums，一个运算符栈 ops数字先放着，运算符也先放着；一旦确定栈顶运算符已经应该被计算，就立刻把它应用到数字栈顶的两个数上。
遍历表达式时：
- 遇到数字，就解析完整多位数并压入
nums；
- 遇到
(，直接压入ops，表示开启一个新的括号作用域；
- 遇到
)，就不断计算栈顶运算符，直到遇到(；
- 遇到普通运算符
+ - * /，就看它和ops栈顶运算符的优先级关系。 如果 栈顶运算符优先级>=当前运算符，就先计算栈顶；然后再把当前运算符压栈。
例如，
6 - 4 + 2 ：加减优先级相同，并且计算顺序是从左到右。
所以当我们遇到
+ 时，如果栈顶是 -，必须先算掉 6 - 4，再处理后面的 + 2。因此，只要 栈顶运算符优先级
>= 当前运算符，就应该先计算栈顶。当然，如果栈顶是 (，就不能跨过括号计算。Walk Through Example
以
2 * (5 + 5 * 2)为例：先读到
2 和 *，它们分别进入数字栈和运算符栈。
遇到 ( 时，说明进入一个新作用域，把 ( 压入运算符栈。
括号内继续正常计算：5 * 2 会先于加法被计算，括号内部最终得到 15。
遇到 ) 时，把括号内剩余运算都算完并弹出 (，此时括号整体已经变成一个数字 15。
外层再继续计算 2 * 15，得到结果 30。复杂度分析
设
n 是表达式长度- 时间复杂度：
O(n)
每个字符最多被扫描一次，每个运算符最多入栈、出栈一次。
- 空间复杂度：
O(n)
最坏情况下，数字栈和运算符栈都可能存储线性数量的元素。
解法二：递归 （推荐）
每个括号内部，本身就是一个完整合法表达式。把括号内部当成子表达式求值， 更贴近括号的语义。
括号天然对应递归层级，所以我们可以写一个
helper()，它从当前位置开始计算。当遇到 ( 时，递归调用 helper() 计算括号内部的值；当遇到 ) 时，说明当前这一层表达式结束，返回当前层的计算结果。括号表达式被递归求值后，会变成一个普通数字
num，再交给外层按 Basic Calculator II 的栈逻辑处理。可以理解成：
比如
2 * (5 + 5 * 2) ：外层读到
2 * 后遇到 (，递归进去计算 5 + 5 * 2，返回 15。外层拿到 15 后，就像原表达式是 2 * 15继续按照无括号表达式处理。
具体做法：
先在字符串末尾补一个哨兵运算符，方便处理最后一个数字。
扫描表达式的字符时：
- 用
sign记录 当前数字前面的符号。
- 如果遇到数字，就构造完整数字
num；
- 如果遇到
(，递归调用helper()，把括号内部结果当成一个普通数字；
- 如果遇到运算符，就根据
sign处理当前数字。
- 遇到
)时，当前层结束，返回sum(stack)。
它不用维护两个栈，只在每一层维护当前表达式的
stack / num / sign；先用 Basic Calculator II 的思路处理没有括号的表达式：加减直接入栈，乘除立刻和栈顶合并，最后求和。对于括号，把括号内部看成一个独立表达式；遇到
( 就递归计算它，返回值当成当前数字继续处理；遇到 ) 就结束当前递归层并返回当前层的结果。复杂度分析
- 时间复杂度：
O(n)
全局指针
i 从左到右移动，每个字符只会被处理一次。- 空间复杂度：
O(n)
递归调用栈和每层内部的栈在最坏情况下总共可能达到线性规模。
总结
这题是在 Basic Calculator II 的基础上增加括号。没有括号时，我们可以用一个栈把表达式转成若干加法项之和：
+ 把数字压栈，- 把负数压栈，* / 先和栈顶计算再压回去。括号出现后，需要同时处理 运算符优先级 和 括号作用域。 两种解法区别在于处理括号的方式不同：
- 双栈：更像一个通用表达式求值器 用一个全局运算符栈记录括号和优先级； 遇到右括号时，把括号内的运算一次性清空。
- 递归：更贴合括号的语义
每遇到左括号，就进入一个新的
helper()； 遇到右括号时，返回当前helper()的结果。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-772-基础计算器-iii
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 737] 句子相似性 II
下一篇
[Leetcode 1169] 无效交易