预计阅读时间：3 分钟
栈
表达式解析是栈的看家副本：数字栈、符号栈、递归下降，三件套凑齐就能通关四则运算全系列。本合集收录栈类题目。
表达式解析
leetcode 1006
逆波兰一般要维护数字、操作符两个栈；这题操作符顺序是固定循环的，可以省掉操作符栈。乘除是连着算的，加法单独算，减法减的总是一段乘除的结果，按此模拟即可。需要注意负数除法的取整方向。
leetcode 394
可以用栈迭代模拟，也可以 dfs。这里新学了一个名词：这种 dfs 叫递归下降解析——「下降」指从最高层级一层层往下匹配，是处理嵌套结构的标准方式。
它的特点是维护一个全局 index 扫描字符串。相比每次去搜索匹配的右括号（$O(n^2)$），全局 index 保证每个字符只被处理一次，整体 $O(n)$，效率最高。注意遇到终止符（本题是 ]）必须立刻返回，避免递归在内层死循环，由外层负责跳过终止符（全局 index 加一）。
leetcode 224
递归下降或单栈都可以。本题没有优先级问题，单栈更简单；递归下降解析处理纯嵌套还行，处理计算不太直观。
带括号加减乘除（有优先级）的统一直观解法是双栈：一个存数字，一个存运算符。处理优先级的核心一步：当前符号优先级低于栈顶符号时，先用栈顶符号计算，算完再把当前符号入栈——保证高优先级运算先做完。
注意开头为负数的两种情况，都靠补 0 解决：
- 字符串开头是负号，前面补 0；
- 括号里开头是负号，前面补 0。
leetcode 227
简化版四则运算，没有括号，套上面的双栈思路非常简单。
leetcode 772
带括号的完整四则运算。括号的处理方法：左括号无条件入符号栈；遇到右括号就持续计算，直到把左括号弹出为止。
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。