后缀表示法是对栈的典型应用，所谓后缀表示法就是将我们平时所用的四则运算表达式（中缀表示法）以不需要括号，表示成计算机容易理解的形式。这样说很抽象，下面举个例子：
9 + (3 - 1) X 3 + 10 / 2
这就是中缀表示法，也是我们平时书写的四则运算的标准形式，之所以叫中缀，是因为运算符都在两个运算数字的中间。而将运算符放在两个需要计算的数字后面，自然就叫后缀表示法了，比如上面的表达式转换为：
9 3 1 - 3 * + 10 2 / +
1、后缀表达式如何计算？
先不管后缀表达式是怎么来的，先来看为什么前面说后缀表达式适合计算机理解？计算机理解的规则如下：
1、从左到右遍历后缀表达式的每个数字和符号；
2、遇到数字进栈；
3、遇到符号就将栈顶两个数字出栈，并计算，计算的结果进栈；
4、重复2、3直到遍历结束，获得最终结果。
比方说前面的后缀表达式 9 3 1 - 3 * + 10 2 / +，计算过程是这样的：
1、9 3 1都是数字，依次进栈，栈中内容为：9 3 1；
2、遇到“ - ”符号，那么3 1出栈，计算得到2进栈，栈中内容为：9 2；
3、接下来3进栈，栈中内容为：9 2 3；
4、遇到“ * ”符号, 2 3出栈，并计算得到6进栈，栈中内容为：9 6；
5、又遇到“ + ”符号，9 6出栈，计算得到15进栈，栈中内容为：15；
6、接着数字10 2进栈，栈中内容为：15 10 2；
7、遇到符号“ / ”，10 2出栈，计算得到5进栈，栈中内容为：15 5；
8、遇到最后一个符号“ + ”，15 5出栈，计算得到20，遍历结束，结果为20。
从上面的过程来看，计算机只需要一次遍历加上一个栈就可以计算出来表达式的值，后缀表达式确实利于计算机理解，也省掉了烦人的括号！
2、中缀表达式如何转换为后缀表达式？
但是实际上人们书写的时候肯定还是写便于人类理解的中缀表达式，那么计算机在理解中缀表达式的时候，实际上是先将中缀表达式转换为它容易理解的后缀表达式，再依据前面描述的规则进行计算的。中缀表达式转换为后缀表达式的过程也需要用到栈，规则如下：
1、从左到右遍历中缀表达式的每个数字和符号；
2、遇到数字输出，成为后缀表达式的一部分；
3、遇到符号，如果符号是左括号，或者符号的优先级比栈顶元素高，那么该符号进栈；如果符号是右括号，那么栈里必然存在左括号，将栈中符号依次出栈并输出作为表达式一部分，直到左括号出栈（括号不用输出）；如果符号的优先级小于或等于栈顶元素，那么栈中符号依次出栈并输出作为表达式一部分，直到符号的优先级大于栈顶元素为止，同时该符号进栈。
4、重复2、3直到遍历结束，如果此时栈不为空，那么依次栈中符号出栈，输出作为表达式最后一部分。
比如说9 + (3 - 1) X 3 + 10 / 2的转换过程如下：
1、9是数字，输出，表达式为：9；
2、“ + ”进栈，“ ( ”进栈，栈内容为：+ (；
3、数字3输出，表达式为：9 3；
4、“ - ”进栈，栈内容为：+ ( -；
5、数字1输出，表达式为：9 3 1；
6、遇到“ ) ”，根据规则，栈中符号出栈直到“ ( ”出栈为止，此间遇到“ - ”需要输出，因此表达式为：9 3 1 -，栈中内容为：+；
7、遇到“ X ”，由于它的优先级比栈顶元素“ + ”高，因此它进栈，栈中内容为：+ X；
8、遇到数字3输出，表达式为：9 3 1 - 3；
9、之后是“ + ”，优先级比栈顶的“ X ”低，“ X ”出栈输出，“ + ”变成栈顶，栈顶的“ + ”优先级并不大于外面的“ + ”，因此也需要出栈输出，此时栈为空了，那么表达式为：9 3 1 - 3 X +，同时外面的“ + ”进栈，栈中内容为：+；
10、遇到10输出，表达式为：9 3 1 - 3 X + 10；
11、遇到符号“ / ”，优先级比栈顶元素“ + ”高，进栈，栈中内容为：+ /；
12、数字2输出，表达式为：9 3 1 - 3 X + 10 2；
13、遍历结束，栈不为空，栈中符号依次出栈输出，最后表达式为：9 3 1 - 3 X + 10 2 / +。
网友评论