【CPP】栈，后缀表达式与计算

我们平时计算时列的计算式叫做中缀表达式，即运算符放在两个运算数中间的计算式（例：1+1）。但是，这样的式子计算机并不能很好的理解，在遇到有括号加入时就会更难进行编程，于是在这样的需求下，另一种计算式被发明了：后缀表达式。他一开始是由波兰科学家Lukasiewicz发明的前缀表达式（波兰表达式），运算符放在两个运算式之前（例：+11），后来被人将运算符放在了后面，被称为逆波兰表达式即后缀表达式（例：11+）。

栈(stack)，一种先进后出的数据结构，即一种插入和删除都在统一端的线性表，在现实生活中类似于垒盘子，我们最后放上的盘子将会在最早被拿出来。栈可操作的一端称为栈顶，另一端称为栈底，插入称为进栈(push)，删除称为出栈(pop)，在上一篇文章中，我们制作的链表即有可当作栈操作用的函数。在这个表达式变换中，栈是重要的数据结构。

那么，我们先简单地写一个栈类。

在这个类中，由于下面的程序要用到储存char类型和float的数据，所以用了个结构体来储存，再用id来表示元素的类型，这个栈由数组实现，因为本身并不是很难实现，实现方法基本也都在上篇文章中了，主要就是在里面多了个trans()函数，用于下面的程序来反转栈，本身也只是反向拷贝一次，没有什么难点。用移动的p_now指针来标识栈顶的位置。

接下来的重点，是如何将中缀表达式转化为后缀表达式。

首先，我们初始化两个栈，一个用于存放转换完成的式子（目标栈），另一个用于暂时存放操作符（操作符栈），并用一个字符指针来扫描字符串，用一个int来表示目前的扫描状态。

然后，在扫描表达式时，有一下规则：

1. 若扫描到数字，直接压入目标栈中。
2. 若扫描到操作符
3. 若为左括号，直接压入操作符栈中
4. 若为右括号，将操作符栈的数据不断弹出直到遇到一个左括号为止，然后舍弃那个左括号
5. 若为其他操作符
6. 若操作符栈为空或栈顶为左括号，则直接压入操作符栈
7. 若目标操作符优先级高于操作符栈栈顶操作符，则直接压入操作符栈
8. 若目标操作符优先级低于于操作符栈栈顶操作符，则先弹出操作符栈栈顶的操作符并将其压入目标栈，然后再进行一次比较直到结束。

上面是中缀表达式的基本扫描方法，但是这样还不能扫入超过两位的数字或小数，于是多加的flag变量就是这个用途。

1. 当扫描到小数点时，flag--，让flag变成从-1开始的负数，然后用循环将后面的数字循环*0.1变成小数，加到原有目标栈顶的数字上。
2. 当扫描到数字且flag！=0时，让flag变成1，且当flag==1时，先将目标栈顶的数字*10，然后加上现在扫描到的数字，然后重新压入栈中。
3. 当扫描到的不是以上两种情况时（正常操作符），将flag变为0，然后正常操作。

这便是扫描数字的方法。

然后是扫描其他操作符及操作。

这样我们便完成了转换中缀表达式的步骤了。然后就是如何计算后缀表达式呢。这是更简单的操作，方法就是先将刚才的后缀表达式栈反转（代替从1开始扫描），然后一个个数据弹出，由于每两个数字必然匹配一个操作符，当扫描到数字时，压入一个数字栈中，然后每当扫描到操作符，弹出数字栈顶的两个数字，后弹出者置前，前弹出者置后，与操作符进行运算，然后结果压入数字栈中，由此重复，到最后数字栈中会只剩一个数据，数字栈的栈顶数据就会是这次运算的结果。

我们检验一下：

结尾给一下全部代码：http://pan.baidu.com/s/1ge6uM1H 密码：owa2

啊，时间过的真快，要不要写三消的教程呢，真是麻烦呀。