什么是前缀式，中缀式，后缀式

Posted on Wed, 25 Dec 2024 10:35:10 +0800 by LiangMingJian

什么是前缀式

前缀式又称波兰式，是一种没有括号的算术表达式。前缀式将运算符写在前面，操作数写在后面，例如：

算式：1 - ( 2 + 3 ) === - 1 + 2 3

中缀式就是平时人们常用的算术表示方法，操作符处于操作数的中间，例如：

算式：1 - ( 2 + 3 )

后缀式又称逆波兰式。与前缀式不同的是，后缀式把运算符写在运算对象的后面，例如：

算式：1 - ( 2 + 3 ) === 1 2 3 + -

我们知道中缀式是人类所使用的算术表达式，这种方式简单直接。但是如果将这种方式应用到计算机系统中时，则其性能就显得不够优秀了。

众所周知，计算机系统常使用栈来存储数据，而栈的一大特点就是后进先出。

基于栈后进先出的特点，如果我们仍然使用中缀式进行计算，则会造成极大的性能浪费，比如下面的示例：

基于中缀式，使用栈计算 1 - ( 2 + 3 ) * 4。
第一：构造两个栈，记为数字栈 A 和运算栈 B，分别存放数字和运算过程。
第二：从左到右，依次扫描算式。
第三：1 进栈 A，- 进栈 B。
第四：扫描到括号时，因为括号内优先计算，所以在括号闭合前，所有扫描内容进入运算栈 B，即 ( 进栈 B，2 进栈 B，+ 进栈 B，3 进栈 B，) 进栈 B。
第五：当括号闭合，即 ) 进栈 B 或被扫描到时，可以计算括号内的内容，对括号内的内容后进先出的出栈，出栈顺序有 ) 3 + 2 (，丢弃括号，计算 2+3，将结果 5 进栈 A。
第六：继续扫描，* 进栈 B，4 进栈 A。
第七：当所有结果扫描完毕后，此时，栈 A 元素 1, 5, 4，栈 B 元素 -, *。
第八：基于后进先出，依次计算 5 * 4，结果 20 入栈 A，再计算 1 - 20 得出结果。

在计算机计算时，从栈抛出的数，先出的是右操作数，比如减法运算，第一个从栈弹出的数作为被减数，第二个从栈弹出的数作为减数，所以有 1 - 20。

显然，在上面中缀式计算时，使用到了两个栈，而且需要频繁的进行出栈入栈的操作，这显然容易造成资源浪费。

前缀式和后缀式的出现就是为了避免上述中缀式这种情况的出现，比如下面的示例：

基于前缀式，使用栈计算 - 1 * + 2 3 4 的流程和上面后缀式的流程基本一致，只是扫描顺序变更为从右到左而已。

显而易见，不同于中缀式计算，后缀式计算只用到了一个栈，同时入栈出栈操作也变少了。

因此，前缀式和后缀式的出现是为了让计算机系统更高效、更简单地进行计算，解决中缀式计算中的运算符优先级和括号依赖问题。

前缀式和后缀式都可以通过中缀式来进行相互转换，一般建议的转换顺序为：前、后缀式 - 中缀式 - 后、前缀式。

中缀式通过构造二叉树来转换前缀式和后缀式，例如算式：( 1 + 2 ) * 3 + 2 * 1

转换前缀式时

使用先序遍历，从根节点开始，从左往右，左子树永远比右子树先遍历。

最后得出前缀式 + * + 1 2 3 * 2 1

转换后缀式时

使用后序遍历，从左子树开始，然后右子树，最后才是根，根节点在最后面。

最后得出后缀式 1 2 + 3 * 2 1 * +

转换中缀式时

使用中序遍历，从左子树开始，然后根，最后右子树，根节点永远在中间。

最后得出中缀式 ( 1 + 2 ) * 3 + 2 * 1

二叉树的遍历方式可以查看文章：二叉树的度和遍历方式