预计阅读时间：5 分钟
栈
表达式解析是栈的看家副本：数字栈、符号栈、递归下降，三件套凑齐就能通关四则运算全系列。本合集收录栈类题目。
表达式解析
leetcode 1006
中缀表达式求值一般要维护数字、操作符两个栈；这题操作符顺序是固定循环的，可以省掉操作符栈，只留一个数字栈：乘除和栈顶连着算，加号把数正着入栈，减号把数取负入栈，最后求和。需要注意负数除法的取整方向：题目里的数都是正数，但减号后的那段乘积以负数入栈后再做除法，Python 的 // 向下取整（-42 // 5 == -9），而这里要的是先算正数的商再取负（-8），得写成 int(a / b) 或对绝对值做除法。
leetcode 394
可以用栈迭代模拟，也可以 dfs。这里新学了一个名词：这种 dfs 叫递归下降解析——每种语法结构对应一个函数，从最外层的规则开始，一层层递归调用内层规则（「下降」），是处理嵌套结构的标准方式。
它的特点是维护一个全局 index 扫描字符串。相比每次去搜索匹配的右括号（$O(n^2)$），全局 index 保证每个字符只被处理一次，整体 $O(n)$，效率最高。注意遇到终止符（本题是 ]）必须立刻返回，否则内层会越过自己的边界、把外层的内容也吞进来；由外层负责跳过终止符（全局 index 加一）。
leetcode 224
递归下降或单栈都可以。本题只有加减（同一优先级）和括号，单栈更简单；递归下降解析处理纯嵌套还行，处理计算不太直观。
带括号加减乘除（有优先级）的统一直观解法是双栈：一个存数字，一个存运算符。处理优先级的核心一步：当前符号优先级小于或等于栈顶符号时，用 while 循环弹出栈顶符号计算，直到符号栈为空、栈顶优先级更低或栈顶是左括号，再把当前符号入栈——保证高优先级运算先做完。「等于」也要先算，因为加减乘除都是左结合：1-2+3 读到 + 时必须先算出 1-2，否则会算成 1-(2+3)。
注意开头为负数的两种情况，都靠补 0 解决：
- 字符串开头是负号，前面补 0；
- 括号里开头是负号，前面补 0。
leetcode 227
简化版四则运算，没有括号，套上面的双栈思路非常简单。没有括号时也可以只用一个数字栈，做法同 1006：乘除和栈顶连算，加减把带符号的数入栈，最后求和。
leetcode 772
带括号的完整四则运算。括号的处理方法：左括号无条件入符号栈，比较优先级时它当作最低，遇到它就停止弹出；遇到右括号就持续计算，直到把左括号弹出为止。
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。