解析一个算术表达式
基于这么多年的学习，看到1+2*3-4这样的表达式，我们可以很快的想到这是一个算数表达式，使用四则运算的法则就可以得到最后的结果为2，这仅仅是由于我们固定思维（或者是学习沉淀）得出来的结果。如果将这一段字符串交给计算机，并且让它输出我们想要的结果，计算后的结果，就需要将四则运算法则告诉计算机，然后根据这个规则来解析这个表达式，最后它才能给出来我们想要的结果。
从一个纯文本表达式到最后正确的结果这个过程，可以理解为是一个翻译，将文本翻译成算术表达式，在四则运算的规则下，对这个表达式进行它语法下的运算，最后得出正确的结果。
这个简单的四则运算仅仅是一个缩影，往大了就会涉及到json的解析、解释器模式、编程语言的编译等等。这篇文章就将从解析一个算术表达式开始，来对涉及到的深层知识做一个整理。
1. 解释器模式
解释器模式中有四个主要角色：client、expression、context、interpret。其中context会用来保存所有的数据，expression为抽象表达式，又分为终结、非终结表达式，解释器是用来完成具体文本转换的，而client是客户端角色，负责调用。
2. 解释器和编译器
解释器和编译器可以看作是同一个概念，但是他们还是有些差别的。
同样是将源码进行翻译成高级语言进行运行，编译器中分为两步：预处理和处理，而解释器只需要一步处理。并且编译器在翻译的过程中会将源码转化成机器代码，而解释器不会将源码转化成机器代码。
token
AST
3. 逆波兰表达式
逆波兰表达式(Reverse Polish Notation)又叫做后缀表达式，一个正常的表达式使用逆波兰表达式进行转化的结果为：
| 正常表达式 | 逆波兰表达式 |
|---|---|
| a+b | a,b,+ |
| a+b-c | a,b,c,-,+ |
| a+(b-c)*d | a,b,c,-,d,*,+ |
| a+d*(b-c) | a,d,b,c,-,*,+ |
使用逆波兰表达式进行计算的时候只会进行两种简单操作：入栈和出栈，即push、pop。比如，当前字符为变量的时候进行入栈，如果是运算符，将栈顶的两个元素弹出来做运算，然后将结果进行入栈，直到将表达式扫描完，栈里面的值就是表达式的结果。从这个操作过程可以看出来，逆波兰表达式用于计算的时候使用到了栈这一数据结构。
在四则运算解析中，会使用二叉树这种数据结构来抽象表达式，将表达式抽象成二叉树，然后进行中序遍历就可以得出来最后的结果。
3.1 前、中、后序遍历
对于树的这三种遍历方式的特点如下：
- 前序遍历是
先根节点，然后左节点，最后右节点 - 中序遍历是
先左节点，然后根节点，最后右节点 - 后序遍历是
先左节点，然后右节点，最后根节点
我们将所有的表达式使用抽象语法树的形式来表示，对应上面的几个表达式分别如下图，并且得出来它们的前、中、后序遍历结果。
todo：这里放三个图的遍历结果。
从上面的图中可以看出来中序遍历的结果基本上就是我们可以直观理解一个表达式的意思，而前序和后序遍历的结果则不是，但是这两种遍历结果却是对计算机很友好的方式。其中前序遍历的结果得到的表达式是波兰表达式，后序遍历得到的表达式是逆波兰表达式。
基于中序遍历对计算机不友好的原因，很多面试题中会涉及到将中序遍历的结果转换成后序遍历这样的问题。由于这里的四则运算中有优先级这个限制条件，因此中序遍历得出后序遍历不具备唯一性可以打破，这个在后面会进行探究学习。
3.2 逆波兰表达式求解算术表达式
下面将表达式使用逆波兰表达式进行计算结果，这里面主要会用到的数据结构为栈。逆波兰表达式进行入栈的时候是从左往右依次进行遍历，遇到非运算符就入栈，遇到运算符，就将栈顶的两个元素（这两个元素肯定是非运算符类型的，如果不是，就是得出来的逆波兰表达式是错误的）依次弹出来，进行运算（后弹出来的在运算符的前面），计算结果再次入栈，然后继续遍历逆波兰表达式，直到将表达式遍历完，栈里面的值就是最后的结果。
以a+(b-c)*d为例，使用逆波兰表达式，得到的结果为：abc-d*+，每一步的过程描述如下：
- 从左至右扫描，依次将abc入栈
- 遇到
-号，将栈顶的两个元素出栈，执行b-c，得到的结果为B，将B入栈，此时栈内元素为aB - 接着入栈d，栈内元素为aBd
- 遇到
*号，将栈顶的两个元素弹出，执行B*d，得到结果为D，将D入栈，此时栈内元素为aD - 遇到
+号，将栈顶的两个元素弹出，执行a+D，得到结果为A，将A入栈，此时栈内元素为A - 由于整个逆波兰表达式已经遍历完成，栈内的A就是最后的结果
将abcd换成数字进行一遍校验，比如2+(5-3)*4，得到的逆波兰表达式为：253-4*+，每一步的描述为：
- 253入栈
- 遇到
-号，执行5-3，得到2，入栈，栈内为22 - 4入栈，栈内元素为224
- 遇到
*号，执行2*4，得到8，入栈，栈内为28 - 遇到
+号，执行2+8，得到10，入栈，栈内为10 - 最后的结果就是10
可以看出来，使用逆波兰表达式来进行计算会很简单（同样的，使用波兰表达式也很简单），关键是要找到抽象语法树的中序遍历结果，前面说到，中序遍历结果基本上就是四则运算表达式的本来样子，因此，一个方法是通过遍历这个四则运算表达式来得到逆波兰表达式，也就是说要进行中序遍历到后序遍历结果的转换。
3.3 中序遍历转后序遍历
当有一个tree的中序遍历结果时，要转换成对应的后序遍历需要两个栈，一个用来存储运算符，一个用来存储中间结果。
还是以上面的a+(b-c)*d例子来进行分步描述：
| 扫描到的字符 | stack-1(存储结果) | stack-2(存储运算符) | 分步说明 |
|---|---|---|---|
| a | a | 空 | 扫描到非运算符，直接入s1 |
| + | a | + | 扫描到+运算符，入s2，并且s2为空，不需要弹出来其他同级别运算符 |
| ( | a | +( | (运算符，直接入s2 |
| b | ab | +( | 非运算符，直接入s1 |
| - | ab | +(- | 扫描到-运算符，由于s2顶部不为它的同级别运算符，直接入s2 |
| c | abc | +(- | 非运算符，直接入s1 |
| ) | abc- | + | 扫描到)运算符，弹出s2内顶部元素，直到将第一个(运算符弹出为止，弹出的元素依次入s1 |
| * | abc- | +* | 扫描到*运算符，由于s2顶为+运算符，不是*的同优先级运算符，直接入s2 |
| d | abc-d | +* | 扫描到非运算符，直接入s1 |
| 扫描完毕 | abc-d*+ | 空 | 由于已经遍历了字符串的所有内容，因此，将s2中的元素依次弹入到s1内部，得到最终的s1中的值就是逆波兰表达式 |