310计1 表达式求值.doc

例3.3 表达式求值表达式的计算与括号匹配一样是程序设计语言编译系统中的一个基本问题，它的实现是堆栈应用的一个典型实例。任何一个表达式都是由运算对象（也称操作数）和运算符（也称操作符）以及分界符组成的。这些运算对象、运算符以及分界符称为单词。根据运算符的类型，通常可以把表达式分为逻辑表达式、关系表达式和算术表达式三类。为了简化问题而又不失一般性，这里仅仅讨论只含二元运算符的算术表达式的求值问题，读者不难将它推广到一般表达式。先要说明的是，通常在数学中看到的或者出现在程序中的算术表达式都称为中缀表达式，中缀表达式中的运算符一般出现在两个运算对象之间（单目运算符除外）。例如，a-(b+c*d)/e在计算机系统内多遍处理的编译程序中，在处理这样的表达式并将其生成一系列机器指令或者直接求值之前，往往先将它变换成另外一种形式，即后缀表达式形式。顾名思义，后缀表达式就是表达式中的运算符出现在运算对象之后。在后缀表达式中，不存在括号，也不存在运算符优先级的差别，计算过程完全按运算符出现的先后次序进行；整个计算过程仅需一遍扫描便可完成，比中缀表达式的计算简单得多。例如，前面给出的中缀表达式写成后缀形式为：abcd*+e/-这样处理的好处是：编译程序处理表达式时，首先从左至右一次扫描后缀表达式的各个单词，如果读到的一个单词为运算符，就对该运算符前面的两个运算对象施以该运算符所代表的运算；然后将结果存入一个临时单元Ti中（i1），并作为一个新的运算对象重复进行上述过程，直到表达式处理完毕。例如：abcd*+e/-的运算过程如表3.1所示。 表3.1 后缀表达式的计算过程操作顺序后缀表达式T1c*dabT1+e/-T2b+T1aT2e/-T3T2/eaT3-T4a-T3T4从上面的讨论知道，后缀表达式之所以容易被编译程序处理，是由于它具有以下特点：（1） 后缀表达式中不出现括号；（2） 后缀表达式与中缀表达式的运算对象的先后次序相同，只是所读到的运算符先后次序可能有所改变。正是由于后缀表达式具有以上特点，所以，处理时不必考虑运算符的优先关系。在具体的处理过程中，需要设置一个堆栈，用来保存已经读到的运算对象。也就是说，从左至右依次扫描后缀表达式，每读到一个运算对象就将其压入堆栈；每读到一个运算符，就从堆栈中取出相应的运算对象进行该运算符所代表的操作，并把运算结果作为一个新的运算对象压入堆栈。表达式最后的计算结果就是位于堆栈中栈顶的值。综上所述，表达式的值的计算过程需要经过两个步骤：一是把中缀表达式变换为后缀表达式；二是根据后缀表达式产生计算表达式的机器指令序列。相对而言，第二个步骤较为简单些，我们先讨论实现第二个步骤的算法。算法3.8 #includeseqstack.cVoid evalution() char c; int op1,op2,c1,result,x=0,val();seqstack *opd; /*栈opd存放操作数及计算结果*/initstack(opd); /*初始化栈*/printf(“请从键盘输入后缀表达式：”）；while(c=getchar()!=n) /*后缀表达式未结束*/ if(c= ) continue; /*空格则读入下一个字符*/ if(c=0)&(c、-*/(#opt1,则将opt2进栈，然后读下一个单词；如果opt2opt1，opt1退栈作为后缀表达式中的一员输出。此后，继续比较opt2与opt1的优先级（注意，此时的opt1已经不是先前的那个运算符了），直到opt2得到合适的处理。如果opt2=opt1,并且opt2“#”，则opt1退栈且消去opt2，然后继续读下一个单词，重复以上步骤，直到opt1=“#”、opt2=“#”时，算法结束。算法3.10#includeseqstackzztohz()/*设opt为运算符栈，op为运算符集合，super（）为运算符优先比较函数*/seqstack *opt;char c,x;initstack(opt);push(opt,#);c=getchar();while(c!=# | gettop(opt)!= #) if(!In(c,op) putchar(c); /*不是运算符就将其作为后缀表达式的部分输出*/ c=getchar（）; else switch(super(gettop(opt),c) case :putchar(pop(opt,x);/*栈顶元素优先权高，栈顶元素退栈并输出为后缀表达式*/break; 利用上述算法，中缀表达式a-(b+c*d)/e转换成后缀表达式的过程如表3.3所示： 表3.3 中缀表达式转换为后缀表达式示例步骤中缀表达式运算符栈输出（后缀表达式）1a-(b+c*d)/e#2-(b+c*d)/e#a3(b+c*d)/e#-a4b+c*d)/e#-(a5+c*d)/e#-(ab6c*d)/e#-(+ab7*d)/e#-(+abc8d)/e#