后缀(postfix, 也成逆波兰 reverse Polish)表达式在我们的生活中并不常见,在我们日常中见到的,通常都是中缀(infix)式,例如:

3.14 + 15 * (9.2 – 6.5)

这是便于人类理解的表达式,之所以便于人类理解,是因为人从小便接受识别此类表达式的教育,而且这种记号方式将运算符和数字明确的分开,不会产生数字堆叠在一起的混乱情况。
但是对于计算机而言,这样的表达式并不好理解,计算机是一种线性读入信息,线性输出信息的工具,人类所通识的中缀式,对于这种规规矩矩按照顺序计算的工具而言,是不容易理解的。你可能一眼就看出来要先算小括号里的表达式,然后算乘法,最后算加法。而计算机直接读入的话,可能会先算3.14 + 15,这自然是荒谬的,而后缀法就为计算机计算表达式提供了一种非常有效的解决方案。这篇文章主要的内容是介绍如何将中缀表达式转换为后缀表达式。
说了这么半天,后缀表达式又是什么样子呢?它又有什么样的优势呢?
我们现在来看一组对比:
2
后缀表达式为什么会有优势呢?因为计算机线性读入的特征,
我们以第二个表达式为例,以:
用后缀式,在计算机的计算过程就是:

  1. a
  2. a b
  3. a b c
  4. a b c *
  5. a (b * c) 计算出b * c的值记作x
  6. a x +
  7. (a + x) 计算出a + x 的值

就是这样一个符合线性读入过程的运算,这样就合理的解决了运算之间优先关系的处理。
那么如何将一个中缀式装换为后缀式呢?
其实算法很简单,运用之前我介绍过的“栈”就可以轻易达到这个目的,我们使用两个栈,一个是表达式栈,用来存储转换成后缀表达式的结果,一个是运算符栈,用来暂存表达式中的运算符,这个栈满足条件“从栈顶到栈底,运算符的优先级依次下降”,我们以表达式a + b * (c + d) 作为例子,来模拟一下转换的过程:

1.读入数字a,存入表达式栈,紧接着读入运算符+,存入运算符栈

2.读入数字b,存入表达式栈,紧接着读入运算符*,由于*比+运算优先级高,所以也可以存入运算符栈

3.读入左括号(,(具有最高优先级,所以也存入运算符栈,后面的数字c存入表达式栈

4.读入运算符+,存入运算符栈,然后读入数字d,存入表达式栈

5.读入右括号),开始弹出运算符栈中的运算符到表达式栈,直到遇到左括号为止

6.表达式已经读完了,将运算符栈中的运算符全部弹出到表达式栈,至此后缀表达式已经转换完成!

总结下来,基本步骤很明确,就是以下几个步骤:

(1)读入,如果是数字,就置入表达式栈,然后重复(1)。如果是运算符继续
(2)如果是’)’,则将运算符栈中直到’(‘之前的运算符都弹入表达式栈,并弹出’(‘。否则继续
(3)与运算符栈中的栈顶表达式比较,优先级高的话,置入运算符栈。否则将栈内的低优先级运算符弹入表达式栈,然后将新的运算符置入表达式栈。继续
(4)如果所有的字符都已经读入完成,则将运算符栈中的符号全部弹入表达式栈,至此完成转换。否则,回到步骤(1)。

有了这样的算法思路,实现起来那就是非常容,易的事情了。下面给出我写的转换代码,需要注意,我的代码没有处理负号这样的情况,而且对于非法的表达式(比如括号不匹配,两个乘号在一起)也没有进行识别,所以在实用性上还是有所欠缺的。
代码中通过一点简单的方法使得输入表达式的数字可以是浮点型的,表达式以字符串型栈保存,方便以后转换为数字。
以下为代码:

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
  Subscribe  
最新 最旧 得票最多
提醒

老兄,您这段是否有错呢?
bool cmpPRI(char a, char b)
{
//构造优先级表
short priList[48];
priList[”]= 16;
priList[‘(‘] = 1;
priList[‘*’] = 3;
priList[‘/’]= 3;
priList[‘+’] = 4;
priList[‘-‘] = 4;

if(priList[a] < priList[b]) return true;
else return false;
}
是否应该把这句if(priList[a] < priList[b]) return true;改为:
if(priList[a] <= priList[b]) return true;