表达式分类

表达式分为前缀(DLR)、中缀(LDR)、后缀表达式(LRD)三种。 我们平时生活中和数学中使用的基本都是中缀表达式，形如1+2+4∗5 而前缀表达式又称波兰式(称呼而已，不碍事)，如+、+、1、2、∗、4、5 后缀表达式又称逆波兰式(称呼而已，不碍事)，如1、2、+、4、5、∗、+ 在这三种表达式中，所有的叶子节点都一定是数字，非叶子节点则为运算符号。

~~说人话：~~ 运算符号放在哪，就是什么类型的表达式

1+1  //  中缀表达式
+11  //  前缀表达式(波兰式)
11+  //  后缀表达式(逆波兰式)

可以通过栈，将中缀表达式转化为前缀表达式或后缀表达式

接下来，我们要深入挖掘1、如何通过中缀表达式转换为后缀？2、如何求解后缀表达式的值，还是以举例子说明：

我们先来回答疑问2、如何求解后缀表达式的值： 为了解释后缀表达式的好处，我们先来看看，计算机如何应用后缀表达式计算出最终的结果20的。

后缀表达式：9 3 1 - 3 * + 10 2 / +

规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

下面是详细的步骤：

1. 初始化一个空栈。此桟用来对要运算的数字进出使用。
2. 后缀表达式中前三个都是数字，所以9、3、1进栈。
3. 接下来是减号“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈。
4. 接着是数字3进栈。
5. 后面是乘法“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。
6. 下面是加法“+”，所以找中6和9出找，9与6相加，得到15，将15进栈。
7. 接着是10与2两数字进栈。
8. 接下来是符号因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。
9. 最后一个是符号“+”，所以15与5出找并相加，得到20，将20进栈。
10. 结果是20出栈，栈变为空。

果然，后缀表达法可以很顺利解决计算的问题。

接下来，回答疑问1，这个后缀表达式9 3 1 - 3 * + 10 2 / +是如何通过算式9+(3-1)*3+10/2变化而来呢？

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于找顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。 下面我们来具体看看这个过程。

1. 初始化一空栈，用来对符号进出栈使用。

2. 第一个字符是数字9，输出9，后面是符号“+”，进栈。

3. 第三个字符是“(”,依然是符号，因其只是左括号，还未配对，故进栈。

4. 第四个字符是数字3，输出，总表达式为9 3,接着是“-”进栈。

1. 接下来是数字1，输出，总表达式为9 3 1，后面是符号“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”，因此输出“-”，总的输出表达式为9 3 1 -

2. 接着是数字3，输出，总的表达式为9 3 1 - 3 。紧接着是符号“”，因为此时的栈顶符号为“+”号，优先级低于“”，因此不输出，进栈。

3. 之后是符号“+”，此时当前栈顶元素比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为 9 3 1 - 3 * +.然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”，而下图中的栈底（也是栈顶）的“+”是指“9+(3-1)*3+”中的最后一个“+”。

4. 紧接着数字10，输出，总表达式变为9 3 1-3 * + 10。

5. 最后一个数字2,输出，总的表达式为 9 3 1-3*+ 10 2

6. 因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1-3*+ 10 2/+

从刚才的推导中你会发现，要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步： 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。 整个过程，都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com