浅谈表达式的求值（Vol.2 进阶）

[$\color{red}{Warning}$](https://www.luogu.org/blog/tiger2005/qian-tan-biao-da-shi-di-qiu-zhi-hou-zhui-biao-da-shi-post) 在观看本博客之前，请保证自己理解了表达式的三种表达方式。 本文旨在让大家更深层次的了解表达式，基础的知识就是上方的链接中所写的。所以，在了解后缀表达式的运算原理之后，我将不会讲述类似的前缀表达式的运算原理。 ``` Change Logs: 2019-10-27 14:01 修改：加入中缀表达式更快算法的简析 2019-10-27 13:44 修改：加入"知二推一"出现的意义(个人之前没有表述清楚) 2019-10-19 23:08 初稿 ``` ## $ \text{0 目录} $ $\text{¶ 0 目录}$ $\text{¶ 1 浅谈后缀表达式的还原}$ $\text{¶ 2 前缀表达式介绍}$ $\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ¶ I 简单介绍}$ $\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ¶ II 构造方法和还原方法}$ $\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ¶ III 好玩的特性}$ $\text{¶ 3 前中后缀表达式区别和联系}$ $\text{¶ 4 拓展}$ $\text{¶ 5 总结}$ ## $ \text{1 浅谈后缀表达式的还原} $ 我们可以使用后缀表达式来构造表达式树 我们想一下后缀表达式的计算 ``` 后序的时候，假设有一个排列如下： 数字1 数字2 计算符 那么这三个数可以被数字1[计算符]数字2代替（就是一次计算） ``` 我们再回头看一看表达式树的计算 ``` f(左儿子)[now所代表的运算符]f(右儿子) ``` 所以，我们可以想到一种非常像后缀表达式计算的方法： 定义一种树，支持将几棵树用另一个顶点作为根合并起来，就像这样： ``` * + - / \ / \ 1 2 3 4 ------------- * / \ + - / \ / \ 1 2 3 4 ``` 之后我们用一个栈S，利用以上性质计算： ``` inp -> 后缀表达式 struct Tree{...} stack<Tree> S for i from 1 to N if(inp[i]是数字) 定义一个只有该数字的Tree，并加入到栈中 else 创建一个只有这个字符的Tree，之后将栈顶的两棵树以它为根合并 ``` 同时，我们也可以用字符串代替树，那么树的合并相当于字符串拼接，最后得到的是没有括号的中缀表达式。 如果你想加括号的话，不妨利用以下文字，自己思考一下。 ``` 中序遍历就是原式，但是我们通过运算优先级建树，这时候受到括号的影响，计算的优先级会改变（括号里面的优先）。 判断的方式很简单。 就比如除号，它在树中左边是加号，运算符优先级比它小，但是竟然先被计算，所以，加号所在子树左右应该加上括号。 ``` 我们将模拟后缀表达式转中缀表达式帮助你了解，用表达式树的方法同理。 ``` inp > 6 2 3 * + 4 / 5 - 扫到6 Stack > 6 扫到2 Stack > 6 2 扫到3 Stack > 6 2 3 扫到* "2" + "*" + "3" = "(2*3)" Stack > 6 (2*3) 扫到+ "6" + "+" + "(2*3)" = "(6+(2*3))" Stack > (6+(2*3)) 扫到4 Stack > (6+(2*3)) 4 扫到/ "(6+(2*3))" + "/" + "4" = "((6+(2*3))/4)" Stack > ((6+(2*3))/4) 扫到5 Stack > ((6+(2*3))/4) 5 扫到- ((6+(2*3))/4)" + "-" + "5" = "((((6+(2*3))/4)-5)" Stack > ((((6+(2*3))/4)-5) ``` ## $\text{2 前缀表达式介绍}$ $\rightarrow\text{I 简单介绍}$ 前缀表达式，类似于后缀表达式，是表达式的表达方式之一。 和后缀表达式相近，前缀表达式"将运算符写在前面"，从而可以加快运行速度(和后缀表达式一样，在某种枚举顺序下，只使用出栈和入栈，加上基础计算，就可以在$O(n)$的复杂度下运行出结果)。 打个比方，  中，前缀表达式就是`- / + 6 * 2 3 4 5` $\rightarrow\text{II 构造方法和还原方法}$ 刚才讲过，和后缀表达式一样，前缀表达式也支持$O(n)$的计算和还原。区别如下 `>` 后缀表达式的枚举是从左到右，前缀表达式是从右到左 `>` 后缀表达式的计算是[次顶元素][运算符][栈顶元素]，而前缀表达式的计算是[栈顶元素][运算符][次顶元素] 其他的和后缀表达式没有区别。但是，由于从左到右判断代码明显更好些（举例：没有人会选择将已知字符串转为数字的时候倒着处理，这样还需要计算10的幂次），所以个人还是推荐使用后缀表达式处理方法。 ......算了，还是给一下运算举例吧。 ``` - / + 6 * 2 3 4 5 扫到5，加入栈 +------------ | 5| | | | +------------ 扫到4，加入栈 +------------ | 5| 4| | | +------------ 扫到3，加入栈 +------------ | 5| 4| 3| | +------------ 扫到2，加入栈 +------------ | 5| 4| 3| 2| +------------ 扫到*，计算2*3，返回6，把6加入栈中 +------------ | 5| 4| 6| | +------------ 扫到6，加入栈 +------------ | 5| 4| 6| 6| +------------ 扫到+，计算6+6，返回12，把12加入栈中 +------------ | 5| 4|12| | +------------ 扫到/，计算12/4，返回3，把3加入栈中 +------------ | 5| 3| | | +------------ 扫到-，计算3-5，返回-2，把-2加入栈中 +------------ |-2| | | | +------------ 结束，返回-2 ``` $\rightarrow\text{III 好玩的特性}$ 我们不妨将前缀表达式的括号显示，那么就会出现以下事情： ``` -(/(+(6,*(2,3))4),5) ``` 这就像一个个函数一样了，也就是说，一个表达式 ``` minus(divide(plus(6,multiply(2,3))4),5) ``` 可以只通过去括号和逗号就可以转换为前缀表达式！ 所以，That's it ! 我们就可以将一个只由函数和数字组合的表达式只通过拆括号和去逗号的方式转为前缀表达式，在循环运算的时候甚至可以直接跳过这些省略的字符。 因此，我们就找到了一种全新的表达式计算方法： 对于每一个参数数量确定的函数，当参数为组合式的时候，递归处理前缀表达式；是数字的时候直接跳过。由此，我们就可以将一个表达式转换为前缀表达式，从而解决问题。 为什么说数量确定？数量不确定的时候，函数的前缀表达式和其他的表达式一拼起来就会使得表达式出现歧义。 这种方法正好适用于[这道题](https://www.luogu.org/problem/UVA12666)，感兴趣的人可以去做一下。 ## $\text{3 前中后缀表达式区别和联系}$ 特性 | 中缀表达式 | 前缀表达式 | 后缀表达式 :-:|:-:|:-:|:-: 有无括号 | 有 | 无 | 无 运算方法 | 回溯 | 正向枚举 | 反向枚举 是否使用字符优先级 | 是 | 否 | 否 转换(还原) | 单调栈 | 树型数据结构 | 树型数据结构 计算时间 | 一般$O(n^2)$ | $O(n)$ | $O(n)$ 电脑解析难度 | 高 | 低 | 低 别名 | 中缀记法 | 波兰表达式 | 逆波兰表达式 ## $\text{4 拓展}$ 由于之前BB了这么多关于表达式的转换，而且在中缀表达式去掉括号之后这三种表达式就是表达式树的三种基础遍历方式，所以这里利用三种表达式表示法的互相转换和还原解决知二推一的问题。由于死记硬背这些定理不好记住，所以建议和之前介绍的表达式求值和还原法理解。 前中推后：顺序枚举前缀表达式，获取它在中缀表达式中的位置，从而将中缀表达式分成两半，在左右分别继续上面的操作，直到整棵表达式树的形态确定。后中推前同理，只需倒着枚举。 前后推中：顺序枚举前缀表达式，获取它在后缀表达式中的位置，可以知道，后缀表达式中它的位置到它父亲的位置就是它父亲的右半子树的后缀表达式，以此类推。 实际上，除了前传开头提到的中缀表达式计算方法，中缀表达式是存在$O(n)$的计算方法的，在这里简单一提。 在这里，我们可以预先求出括号的匹配关系，之后，在一串表达式中，我们可以使用跳跃括号的方式找到本表达式中最后计算的那些符号(注意，这几个符号的运算优先级应当一样)，将表达式劈成几部分后分别计算这几个表达式，就这样递归下去。由于每一次我们都跳过了括号，所以运算复杂度是$O(n)$的，但是常数随优先级个数而变化(想一想，为什么)。 当然，构造巴科斯范式并使用递归下降法可以让速度达到一个新的高度，这些将会在之后讲到。 ## $ \text{5 总结} $ 在消化了这篇文章以及它的[前传](https://www.luogu.org/blog/tiger2005/qian-tan-biao-da-shi-di-qiu-zhi-hou-zhui-biao-da-shi-post)后，实际上简单的表达式的求值和转换都不是问题了。同时，你也可以将其使用在自创高级语言编译器的解析过程当中，大大加快处理的速度。 最后，完结撒花!!!`*★,°*:.☆(￣▽￣)/$:*.°★* 。`