中缀及后缀算术表达式在运算中的应用研究

摘要:表达式求值是程序设计语言编译中的一个最基本问题。与人们习惯的中缀表示的表达式相比,后缀表达式不存在括号,没有优先级的差别,表达式中各个运算是按照运算符出现的顺序进行的。因此非常适合串行工作的计算机处理方式。该文首先对这两种表达式表示方法进行了分析比较,然后通过具体分析实现这两种表达式求值的算法来论证表达式后缀表示优于中缀表示。最后简要谈一下中缀表达式到后缀表达式的转换。

关键词:中缀表达式;后缀表达式;算符优先;堆栈

中图分类号:TP31文献标识码:A文章编号:1009-3044(2009)32-8921-03

A Study of Index and Suffix Arithmetic Expression in the Operation Applied Research

GUO Meng-meng, XU Yong-chang

(Shandong Yingcai College, Jinan 250104, China)

Abstract: The expression evaluation is the most basic question in programming language translation. Compared with infix expression with which people are familiar, suffix expression does not have the parenthesis, nor does it have the priority difference; each operation is carried out according to the order in which the operator appears. Therefore it is suitable for the serial work of the computer processing mode. This article first analyses and compares these two kinds of expression, then attempts to prove that suffix expression is superior to infix expression through the concrete analysis of the realization of evaluation algorithm of these two kinds of expression. Finally it discusses briefly the transformation of infix expression into the suffix expression.

Key words: infix expression; suffix expression; priority operator; stack

表达式求值是程序设计语言编译中的一个最基本问题。通常书写的算术表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。运算符包括单目运算符和双目运算符两类,单目运算符只要求一个操作数,并被置于该操作数的前面,双目运算符要求有两个操作数,其位置因表示方法不同而有所差异。按照运算符与运算对象的位置关系,算术表达式的表示方法分为前缀表达式、中缀表达式和后缀表达式三种,其中后两者较为常用。为了简便起见,在本文的讨论中只考虑双目运算符(仅+、-、*、/四种)以及括号。

1 分析

中缀算术表达式最为常见,其双目运算符置于与之相关的两个运算对象之间。对中缀表达式的求值,并非按照运算符出现的自然顺序来执行其中的各个运算,而是根据算符间的优先关系来确定运算的次序,此外,还需要顾及括号规则。中缀表达式的计算比较复杂,它必须遵守以下三条规则:

1) 先计算括号内,后计算括号外;

2) 在无括号或同层括号内,先乘除运算,后加减运算,即乘除运算的优先级高于加减运算的优先级;

3) 同一优先级运算,从左向右依次进行。

从以上规则可以看出,在中缀表达式的计算过程中,既要考虑括号的作用,又要考虑运算符的优先级,还要考虑运算符出现的先后次序。因此,各运算符实际的运算次序往往同它们在表达式中出现的先后次序是不一致的,是不可预测的。中缀算术表达式符合人的思维方式,我们凭直观判别一个中缀表达式中运算符运算顺序并不困难,但对于计算机处理起来就比较复杂了。由于传统计算机一维的计算模型,只能一个字符一个字符地扫描,要想确定哪一个运算符优先计算,就必须对整个中缀表达式扫描一遍,一个中缀表达式中有多少个运算符,原则上就需要扫描多少遍才能计算完毕,这样算法的时间复杂性就差了,显然是不可取的。

那么,能否把中缀算术表达式转换成另一种形式的算术表达式,使计算简单化呢? 回答是肯定的。波兰科学家卢卡谢维奇(J.Lukasiewicz)很早就提出了算术表达式的另一种表示,即后缀表示,又称逆波兰式,其定义是把运算符放在两个运算对象的后面。采用后缀表示的算术表达式被称为后缀算术表达式或后缀表达式。在后缀表达式中,不存在括号,也不存在优先级的差别,计算过程完全按照运算符出现的先后次序进行,整个计算过程仅需扫描一遍表达式便可完成,显然比中缀表达式的计算要简单得多。例如,对于后缀表达式“124C5/”,其中‘’字符表示成分之间的空格,因减法运算符在前,除法运算符在后,所以应先做减法,后做除法;减法的两个操作数是它前面的12和4,其中第一个数12是被减数,第二个数4是减数;除法的两个操作数是它前面的12减4的差(即8)和5,其中8是被除数,5是除数。

那么中缀算术表达式转换成对应的后缀算术表达式的基本思想是什么呢?其实很简单,就是把每个运算符都移到它的两个运算对象之后,而后删除掉所有的括号即可。

实际上J.Lukasiewicz最先提出的是表达式的前缀表示方法,即把每一个运算符置于运算对象之前,例如表达式“10+(20-5*3)/(13-8)”其前缀表示形式为“+ 10 / - 20 * 5 3 -13 8”。前缀表达式的优点与后缀表达式的相同,也不含有括号,表达式中的运算也是按照运算符出现的顺序进行的,计算也很容易实现。但由于其表示方法与人们的习惯相差甚远,因而并不常用。

对于简单的中缀表达式我们很容易得到其后缀表达式,但对于较为复杂的中缀表达式就很难从直观上得到其后缀表达式。

我们可以用一棵二叉树来表示算术表达式,非终端结点表示运算符,终端(叶子)结点代表运算对象,如10+(20-5*3)/(13-8),那么按照先序、中序、后序遍历二叉树,就可以分别得到前缀、中缀和后缀算术表达式。如此可以很方便地实现三种算术表达式的相互转换。

用计算机又是怎样实现它们之间的转化的呢?以下是自然语言描述的表达式转前缀算法:

1) 求输入串的逆序。

2) 检查输入的下一元素。

3) 假若是操作数,把它添加到输出串中。继续输入下一个字符。

4) 假若是闭括号(‘)’),将其入栈。继续输入下一个字符。

5) 假如是运算符,则

① 假如栈空,此运算符入栈。继续输入下一个字符。

② 假如栈顶是闭括号,此运算符入栈。继续输入下一个字符。

③ 假如它的优先级高于或等于栈顶运算符,此运算符入栈。继续输入下一个字符。

④ 否则,栈顶运算符出栈并添加到输出串中,重复步骤5)。

6) 假如是开括号(‘(’),栈中运算符逐个出栈并输出,直到遇到闭括号。闭括号出栈并丢弃。继续输入下一个字符。

7) 假如输入还未完毕,跳转到步骤2)。

8) 假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。

9) 求输出串的逆序。

假设我们要将表达式“2*3/(2-1)+5*(4-1)”转换成前缀形式,原表达式的逆序是“)1-4(*5+)1-2(/3*2”,输出串的逆序为“+/*23-21*5-41”,所以,最终求得的前缀表达式是“+/*23-21*5-41”。

2 实现

在计算机中进行算术表达式的求值是通过堆栈来实现的。后缀表达式由于其本身所具有的优点,表达式中各个运算是按照运算符出现的顺序进行的,其计算求值比较简单,扫描一遍即可完成。它只需要使用一个栈,用来存储后缀表达式中的操作数、计算过程中的中间数据以及最后结果。

而具体的求值比较简单,扫描一遍即可完成。它需要使用一个栈,假定用S表示,其元素类型应为操作数的类型,假定为整型int,用此栈存储后缀表达式中的操作数、计算过程中的中间数据以及最后结果。假定一个后缀算术表达式以字符‘$’作为结束符,并且以一个字符串的方式提供。后缀表达式求值算法的基本思路是:把包含后缀算术表达式的字符串定义为一个输入字符串流对象,每次从中读入一个字符(空格作为数据之间的分隔符,不会被作为字符读入)时,若是运算符,则表明它的两个操作数已经在栈S中,其中栈顶元素为运算符的后一个操作数,栈顶元素的下一个元素为运算符的前一个操作数,把它们出栈后进行相应运算即可,然后把运算结果再压入栈S中;否则,读入的字符必为操作数的最高位数字,应把它重新送回输入流中,然后把下一个数据作为整型数据输入,并将其压入栈S中。依次扫描每一个字符(对于整型数据仅需扫描它的最高位并一次输入整个数值)并进行上述处理,直到遇到结束符‘$’为止,表明后缀表达式计算完毕,最终结果保存在栈中,并且栈中仅存这一个值,把它弹出返回即可。用类C++语言描述的表达式后缀表达式求值的算法如下所述:

int postexpression (char* str)

{// 计算由str字符串所表示的后缀表达式的值,表达式要以‘$’字符结束。

stack S;// 用S栈存储操作数和中间计算结果

InitStack(S); // 初始化栈

istrstream ins(str);// 把str定义为输入字符串流对象ins

char ch;// 用于输入字符型数据

float x;// 用于输入整型数据

ins>>ch;// 从ins流对象(即str字符串)中顺序读入一个字符

while (ch! =‘$’)

{ // 扫描每一个字符并进行相应处理

switch (ch)

{case‘+’:x=Pop(S) +Pop(S); break;

case‘-’:x=Pop(S);// Pop(S)弹出减数

x=Pop(S)-x;// Pop(S)弹出的是被减数

break;

case‘*’:x=Pop(S)*Pop(S); break;

case‘/’:x=Pop(S);// Pop(S)弹出除数

if(x! =0.0)x=Pop(S)/x; // Pop(S)弹出的是被除数

else {// 除数为0时终止运行

cerr

break;

default: // 读入的必为一个整型数的最高位数字

ins.putback(ch); // 把它重新回送到输入流中

ins>>x;// 从字符串输入流中读入一个整型数据

}

Push(S,x); // 把读入的一个整型数据或进行相应运算的结果压入到S栈中

ins>>ch; // 输入下一个字符,以便进行下一轮循环处理

}

if (! StackEmpty(S)) // 若栈中仅有一个元素,则它是后缀表达式的值,否则为出错

{x=Pop(S);

if (Stack Empty(S)) return x;

else {cerr

}

else {// 若最后栈为空,则终止运行

cerr

此算法的运行时间主要用在while循环上,它从头至尾扫描后缀表达式中的每一个数据(每个操作数或运算符均为一个数据),若后缀表达式由n个数据组成,则此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于操作数栈的大小,显然,它的最大深度不会超过表达式中操作数的个数,因为操作数的个数与运算符(假定把‘$’也看作为一个特殊运算符,即结束运算符)的个数相等,所以此算法的空间复杂度也同样为O(n)。

中缀表达式求值同样也可以用堆栈来实现,但实现相对于后缀表达式较为复杂,它采用一种称为“算符优先法”的算法,它必须严格按照前面所述的三条规则来进行计算。为了实现算符优先算法,要使用两个工作栈。一个称为OPTR,用以寄存运算符;另一个称为OPND,用以寄存操作数或运算结果,它的基本思想较后缀表达式计算的不同在于:当读取到运算符时并不可能作相应运算,必须首先比较运算符栈中栈顶元素与当前运算符的优先级。若为‘’则作相应运算并将结果入栈。

用类C++语言描述的中缀表达式求值算法描述如下:

int middexpression (char *exp)

{ stack *opnd=new(stack);//操作数栈

stack *optr=new(stack);//运算符栈

char ch=*exp;

int x=0,y,z;

int result;

optrpush(‘$’);

while(ch!=‘$’||optrgettop()!=‘$’)

//字符扫描完毕且运算符栈仅有‘#’时运算结束

{ if(!Operator(ch))//取操作数并入栈

{ x=x*10+(int)(ch)-48;