栈的应用—表达式求值

栈是一种特殊的线性表，它只能在一端进行插入或者删除操作，能进行操作的一端称为栈顶，另一端则称为栈底。利用栈的这个特性，我们可以实现表达式的求值。那么如何利用栈来进行表达式求值呢？关于栈的应用—表达式求值如何实现呢，接下来我们带着问题去学习下面的内容。

利用栈来进行表达式求值有以下两种方式：

一、逆波兰表达式

逆波兰表达式（reverse Polish notation, RPN）又叫做后缀表达式，波兰逻辑学家 J.Lukasiewicz 于1929年提出了这种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表达式。与此相对应的，我们将我们平常所见到的将二元运算符置于与之相关的两个运算对象之间的表达式称作中缀表达式。

举个例子大家就明白了，「1 + 2」就是中缀表达式，若把加号写在最后面：「1 2 +」就是后缀表达式。再来一个复杂点的，中缀表达式「 (1 + 2) * 3 + 4」写成后缀表达式就是「 1 2 + 3 * 4 +」。

这种表示方式简直就是反人类的，为什么呢？因为很容易引起歧义，比如「123+」，我怎么知道这表示的是「1 + 23」还是「12 + 3」？即使是在 12 和 3 之间加一个空格，来让「12 3 +」表示「12 + 3」，但是对我们人类来说还是不够直观。所以这种表示方式在日常生活中并不常见。但是从计算机的角度看，后缀表达式处理起来会更加简便，因为计算机只要自左向右扫描后缀表达式，就可以完成表达式的求值。由于后缀表达式不需要考虑运算符的优先规则，因此求值算法就变得简单了：

1、从左到右依次遍历表达式；

2、遇到数字就直接入栈；

3、遇到操作符就弹出两个元素，先弹出的元素放到操作符的右边，后弹出的元素放到操作符的左边（左边的运算数先入栈，因此后出），将计算得到的结果再压入栈；

4、直到整个表达式遍历完，最后弹出的栈顶元素就是表达式最终的值。

二、中缀表达式转后缀表达式

接下来看看中缀怎么转后缀，我们先对比一下两个表达式：

中缀表达式：2 + 9 / 3 - 5

后缀表达式：2 9 3 / + 5 -

可以看的出来，数字的相对位置是不变的，改变的是符号的位置，那么在转换的过程，我们需要对比各种运算符号的优先级，然后将优先级高的运算符，先输出，低的后输出，这样在后缀表达式求值的时候，就能保存计算顺序不被改变。（左括号和右括号也看成运算符号）具体的算法步骤如下：

1、从左到右遍历中缀表达式；

2、如果是运算数，直接输出；

3、如果是运算符号：若优先级大于栈顶的运算符号（栈不为空），则将该运算符号压入栈中，因为如果该运算符号优先级比栈顶的大，说明要先被计算，那么它是后入的，因此在之后的操作中，一定比栈顶的符号先出，因此在后缀求值中，肯定先被计算；

4、如果是运算符号：若优先级小于等于栈顶的运算符号（栈不为空），则将栈顶的运算符号弹出并输出，然后继续和下一个新的栈顶元素对比，直到优先级大于新的栈顶元素，就将该运算符号压入栈中；

5、左括号：括号里的表达式肯定是要先计算的，因此当扫描到左括号的时候，直接将左括号压入栈中，而入了栈里的左括号，优先级就变到最低了。因为括号里的运算符要先运算；

6、右括号：将栈顶元素弹出并输入，直到遇到左括号（弹出，但不输出）；

7、整个表达式遍历完之后，则将栈里的元素一一弹出并输出。

栈的应用—表达式求值就差不多讲清楚了，事实上栈是一种被广泛应用的数据结构，除了上述的表达式求值之外，栈还用于函数调用及递归实现，回溯算法等等。在适当的时候选择栈，可以更加高效的解决问题。想要了解栈的更多应用可以观看本站的数据结构和算法教程，去探索和发现更多的栈的神奇之处！