【大话数据结构C语言】14 栈的应用 - 四则运算达式求值

系列文章参考资料为《大话数据结构》，源码为个人私有，未经允许不得转载
技术交流群或资料添加微信号：CoderAllen，回复关键字即可

主要用后缀（逆波兰）表达式做栈的现实

0.前言

我们都知道四则运算是很简单，尤其还可以使用计算器，不过对于涉及算式中带有大中小括号的四则运算，这时候简单的计算器就不好用了

比如：

这里边的困难在于乘除在加减的后面，却要先运算，加了括号就变得更复杂了

原理：
不过仔细观察的话，这里边括号都是成对出现的，所以可以利用栈来实现，只要碰到左括号，就将此左括号进栈，不管表达式有多少重括号，反正遇到左括号就进栈，而后面的出现右括号的时候，就让栈顶的左括号出栈，期间让数字运算，这样，最好有括号的表达式从左到右巡查一遍，栈应该是由空到有元素，最后在因全部匹配成功后成为空栈的结果

但是对于四则运算，括号也只是其中的一部分，先乘除后加减使得问题依然复杂，这时候就引出了逆波兰表达式 - 一种不需要括号的后缀表达法

要用后缀表达式应该是

叫后缀的原因是所有的符号都是要在运算数字的后边出现

1.如何获得后缀表达式

我们平时的标准四则远算表达式，叫做中缀表达式

下边就看下

规则：
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；
若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止

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

2.利用栈计算后缀表达式

下边看看计算式是如何计算逆波兰表达式的
1.初始化空栈
2.后缀表达式中前三都是数字，所以 9 3 1 进栈

3.下边的“-”，所以栈中的1 出栈做减数，3出栈做被减数，运算得到2，再把2进栈
4.接着是3进栈

5.后边的乘号“*”，就是栈中的3和2出栈相乘，得到6，在进栈
6.下边的“+”，则6和9出栈相加得到15，在把15进栈

7.然后是10和2两个数字进栈
8.再然后是符号“/”，栈顶的2和10出栈相除得到5，然后5进栈

9.最后一个符号“+”，所以15和5出栈相加，得到20在入栈
10.结果是20出栈，栈变空

从上述推导可以发现，要想计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步
1.将中缀表达式转化为后缀表达式（栈用来进出运算的符号）
2.将后缀表达式进行运算得出结果（栈用来进出运算的数字）

整个过程都充分利用了栈的先进后出的特性，可以非常好的理解栈这个数据结构