【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

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