摘要：在数据结构的处理中经常会碰到对算术表达式的计算。本文首先介绍数据结构中算术表达式的两种表示方法，即中缀表示法和后缀表示法，然后重点介绍了后缀表达式求值的算法和中缀表达式转换为后缀表达式的算法。

　　关键词：数据结构 算术 表达式 中缀 后缀

　　在数据结构中，由算术运算符、操作数和限界符连接而成的式子称为算术表达式。常量、变量和函数可以成为操作数，同时操作数还可以是表达式。运算符包括单目运算符、双目运算符和三目运算符三类。单目运算符只有一个操作数，被放在该操作数的前面，最常用的单目运算符为取正’+’和取负’-’运算符;双目运算符有两个操作数且放在这两个操作数的中间，最常用的双目运算符包括加、减、乘、除和取余等五种，含义与数学上相同;三目运算符只有一个，即为条件运算符，它含有两个字符，分别把三个操作数分开。为简单起见，我们只讨论操作数为整数，含双目运算符加、减、乘、除和()的算术表达式。

　　一、 算术表达式的两种表示

　　根据运算符在表达式中的位置不同，算术表达式有两种表示形式：

　　1、中缀表达式

　　其表示方式为：<操作数><运算符><操作数>。那么当计算机运算一个算术表达式96-4*(5+6)时，编译器并不知道先要运算(5+6)，而是从左到右逐一扫描，当扫描到第一个运算符“-”号时还是无法知道是否可执行，还要继续向右扫描，检查到第二个运算符“*”号，由于“*”号运算级别比 “-”号高，便知道96-4是不能先执行的，再继续向右扫描，检查到“()”号时，由于“()”的优先级别最高，才确定应先执行(5+6)。可见中缀表达式的求值，必须遵守以下三条规则：(1)、先计算括号内，后计算括号外;(2)、在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级;(3)、同一优先级运算，从左向右依次进行。计算机要经过多次扫描，才能求得最后结果。因此，在编译系统中，较少采用中缀表达式，常见的是采用后缀表达式。

　　2、后缀表达式

　　算术表达式的另一种表示，即后缀表示，又称逆波兰式，其定义是把运算符放在两个操作数的后面。采用后缀表示的算术表达式被称为后缀算术表达式或后缀表达式。其表示方式为：<操作数><操作数><运算符>。在后缀表达式中，操作数总在运算符之前，且表达式中无括号和优先级的约束，运算符在后缀表达式中出现的顺序恰为表达式的运算顺序，每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。例如刚才那个中缀表达式96+4*(5+6)对应的后缀表达式就应该是：96 4 5 6 + * +。对这个后缀表达式进行运算时，编译器自左向右进行扫描，当遇到第一个运算符“+”时，就把紧邻“+”号前面的两个操作数取出来进行计算，得到(5+6)的结果，继续向右扫描，遇到“*”号时，再把“*”号前的两个操作数4和11(5+6的运算结果)取出来，得到4*11的结果44，编译器继续向右扫描，遇到“-”号，将96和44进行减法运算，得到最终计算结果52。可见，后缀表达式不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成，显然比中缀表达式的计算要简单得多。

　　需要强调的是，将中缀算术表达式转换成对应的后缀算术表达式的规则是：操作数的顺序不变，按照在中缀表达式中运算符的优先级，将每个运算符都移到它的两个操作数的后面，删除掉所有的括号。

　　二、后缀表达式的求值算法

　　栈又称堆栈，它是一种线性表，运算时仅允许在表的一端进行插入和删除运算，通过“后进先出”的原则依次将栈顶和栈底的数据进行处理。后缀表达式的求值比较简单，扫描一遍即可完成，也可以看成是一种线性操作。所以在对后缀表达式求值时，我们通常需要使用一个栈，开始时栈为空，当从左到右扫描后缀表达式时，若遇到操作数，则进栈，若遇到运算符，则从栈中退出两个操作数，先退出的放在运算符的右边，后退出的放在运算符的左边，然后将运算后的结果再进栈，直到整个表达式运算结束。此时，栈中只有一个数据，该数据即为运算结果，把它弹出返回即完成了运算任务。

　　三、把中缀表达式转换为后缀表达式的算法

　　对于表达式的求值，如果是后缀表达式，可以直接采用上述算法求解;如果是中缀表达式，则可以先将中缀表达转换为后缀表达式，然后再求解。将中缀表达式转换为等价的后缀表达式的转换规则是：

　　1、设立一个栈，用于存放运算符，初始化该栈，一般为了简单起见，先在栈在放入一个优先级最低的结束符“@”;

　　2、从左到右地扫描中缀表达式中的每个字符，针对不同类型的字符按不同的方式进行处理。若扫描到操作数，则直接输出，并输出一个空格作为两个操作数的分隔符;若扫描到运算符，必须与栈顶元素比较，如果此运算符的优先级高于栈顶元素的优先级则进栈，否则，退出栈顶元素并输出，直到高于栈顶则进栈;若扫描到左括号，进栈;若扫描到右括号，则一直退栈输出，直到退到最近的左括号为止。

　　3、当栈为空时，输出的结果即为后缀表达式。

　　例如中缀表达式30+(26+8*3)/15-9转换为等价的后缀表达式，栈的变化及输出结果如下图所示： 读字符 栈中符号 输出结果 说明 30 @ 30 30为操作数直接输出 + @+ 30 +比@优先级高，+进栈 ( @+( 30 (直接进栈 26 @+( 30 26 26为操作数直接输出 + @+(+ 30 26 +比(优先级高，+进栈 8 @+(+ 30 26 8 8为操作数直接输出 * @+(+* 30 26 8 *比+优先级高，*进栈 3 @+(+* 30 26 8 3 3为操作数直接输出 ) @+ 30 26 8 3 * + 遇)，依次退栈输出*和+，退到(，(退栈，但不输出 / @+/ 30 26 8 3 * + /比+优先级高，/进栈 15 @+/ 30 26 8 3 * + 15 15为操作数直接输出 - @+ 30 26 8 3 * + 15/ -的优先级比/低，/退栈输出 @ 30 26 8 3 * + 15/+ -再与栈中的+相比，-的优先级比+低，所以+退栈输出 @- 30 26 8 3 * + 15/+ -进栈 9 @- 30 26 8 3 * + 15/+9 9为操作数直接输出 @ @ 30 26 8 3 * + 15/+9- -的优先级大于@，-退栈输出 30 26 8 3 * + 15/+9- @出栈，栈空结束 转换后的后缀表达式为：30 26 8 3 * + 15 / + 9 -

　　很显然，利用后缀表达式和堆栈技术配合只需要两遍扫描就可完成中缀算术表达式的计算，比直接进行中缀算术表达式计算的扫描次数要少得多。

　　在实际进行中缀算术表达式求值的算法中，把中缀表示转换为后缀表示的算法需要使用一个字符栈来对运算符进行管理，而进行后缀表达式求值的算法又需要使用一个浮点数栈来对操作数进行管理。由于这两个栈的元素类型不同，所以栈的数据类型无法用全局量来定义，即使把栈运算定义成函数也无法适应这种要求。为了解决这个问题，必须把栈的数据类型定义为模板类，把栈运算的函数定义为该类的公用成员函数，通过调用成员函数来实现栈的运算。

 1/2    1 2 下一页 尾页