带优先级的中缀转二叉树
在我们聊具体的算法前，我们先来看一个问题。给定中缀表达式以及各种操作数的优先级，我们如何将这个中缀表达式转换成对应的二叉树。比方说2 + 3 * 6 ，如何在这个中缀表达式的基础上构建二叉树。对于这个问题，我琢磨了很久，总结了三个简单的性质。
- 对于中缀表达式的相邻节点L和R，如果L的优先级高于R，那么L一定是R的左孩子节点。
- 对于中缀表达式的相邻节点L和R，如果L的优先级低于R，那么R一定是L的右子树节点。并且一旦L后续有个节点L‘的优先级小于L，那么L’后续节点不可能再是L的右子树节点了。
- 对于一系列节点，N1，N2 …… Nx如果Nx是第一个优先级小于N1的的节点，那么N2–Nx-1都是N1的右子树节点。
在说完这几条定理以后，让我们来看看构建二叉树的具体算法。另外，我们给出一个定义，对于一个节点，在我们未能决议出它的右子树前，我们称这棵树是不稳定的。根据定理3，一旦我们为N1在找到了一个优先级小于它的节点Nx，那么N1右子树存在哪些节点便能确定了，需要的只是在遍历中缀序列时，对这些节点进行结构化的管理。接下来我们来看具体的算法。
- 初始化：维护一个我们称作右子树库的栈，初始为一节点HＮ，优先级MIN＋１，为序列添加一节点TＮ
- 遍历中缀序列：栈的顶部子树的根节点我们记作R(root)，当前遍历到的节点记作C(current)。
- 如果R的优先级小于C，根据定理2，我们知道C是R的的右子树节点，因此将C推入右子树库中。
- 如果R的优先级大于C，我们维护一个子树，初始为空，用以表示R右子树，记作RT(Right Tree)。进行如下循环，只要栈不为空并且当前R的优先级大于C，我们就将R从栈中弹出，将RT置为R的右子树，并将R任命为新的RT。在循环结束后，将RT置为C的左节点，并将C推入栈中。
- 终止：如果序列遍历结束，ＨＮ的右子树即为我们构造成功的二叉树。
调度场算法
说完了带优先级中缀序列转二叉树，让我们来看看中缀序列转后缀序列。其实既然我们能够还原成二叉树，那么后缀序列也可以很容易得到，因此接下来我们要介绍的调度场算法，原理上其实和之前介绍的算法是有点相似的。
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
可以看到，这个过程与先前讲到的算法过程是很像的。碰到数字就输出，因为数字的优先级最高，意味着它不可能有右子树，所有碰到它我们就输出。碰到符号我们判断与栈顶符号优先级的比较，若是优先级更高，意味着该符号是栈顶符号右子树的一部分，因此入栈；而如果优先级更低，意味着该栈中许多符号的右子树已经确定了。因此我们让所有已经确定的符号出栈输出。
对于括号的处理有点特殊，因为它无法很好的适配我们的二叉树。但是我们可以这样理解，括号意味着括号里面的内容整体就像一个数字一样，因此看到括号就意味着我们需要在一个新的环境里把这个括号里的后缀序列先产生出来，至于这个新的环境也不见得一定要用一个新的栈，只要这个新的环境不影响之前栈的内容即可。因此我们可以让括号的优先级无穷小，并且在看到括号即入栈，只有反括号能够将此括号弹出。这样可以保证这个新环境不会影响之前的环境，因为有这个无限小的括号做隔离。
接下来我们来看看示例
20[(2.44-1.8)/0.4+0.15] -> a((b-c)/d+e)
1 | //1. 在结尾加一结束符： a*((b-c)/d+e)# |