《算术表达式求值（数据结构word版课件）.doc》由会员分享，可在线阅读，更多相关《算术表达式求值（数据结构word版课件）.doc（5页珍藏版）》请在三一文库上搜索。
1、算术表达式求值算术表达式求值是程序设计语言编译中的一个最基本的问题。在程序语言中，运算符位于两个操作数中间的表达式被称为中缀表达式，例如，算术表达式 就是一个中缀表达式。对中缀表达式的运算一般要遵循“先乘除，后加减，从左到右计算，先括号内，后括号外”的规则。中缀表达式不仅要依赖运算符的优先级，而且还要处理括号。为此，我们介绍不需要括号、也没有运算符优先级的后缀表达式的求值过程。后缀表达式是指操作数在运算符的前面，如“”的后缀形式是“” .中缀表达式 后缀表达式1. 后缀表达式求值因为后缀表达式中只有操作数和运算符，所以可以利用堆栈实现表达式求值，其步骤如下：从左到右读入后缀表达式，若读入的是一
2、个操作数，就将它压入堆栈；若读入的是一个运算符，就从堆栈中连续弹出两个元素（两个操作数），不妨设为x和y，计算表达式x y的值，并将计算结果压入堆栈；对整个后缀表达式读入结束时，栈顶元素就是计算结果。波兰后缀表达式的求值算法注：（1）谓词ISOPTOR（x）表示：当x为一操作符时它为真，否则它为假.（2）函数APPLIED（P，x，y）表示操作符P作用于操作数x和y的结果. 例1 波兰后缀表达式的求值算法，假定波兰后缀表达式存储在一维数组Pl : n中算法EPE（P，n）EPE1 堆栈初始化CREATS（S）.EPE2 表达式求值FOR i = 1 TO n DO IF NOT（ISOPTOR
3、（Pi） /Pi为操作数，则压栈 THEN SPi ELSE（yS . xS . SAPPLIED（Pi，x，y）2.中缀表达式转换为波兰后缀表达式接下来，我们讨论如何把一个中缀表达式转换为波兰后缀表达式，即如何把一个操作数-操作符-操作数的序列，转换成一个操作数-操作数-操作符的序列. 下面我们通过一个例子来考察这个转换过程. 中缀表达式 （A+B）*（C-D）* E+F）转换为相应的波兰形式的过程如下： （A+B）*（C-D）*E+F） AB+ CD- CD-E* CD-E*F+ AB+CD-E*F+*上述过程可描述如下：从左到右扫描表达式，当遇到一个操作符时，此时它的左操作数已经转换成波
4、兰后缀表达式，并且在输出序列中；我们用堆栈把该操作符存贮起来，接着继续处理它的右操作数. 如果它的右操作数处理完毕后，则该操作符将被置于栈顶，并同时从栈中弹出该操作符，加到输出序列中. 为了实现上述过程，操作数必须直接加到输出序列中；而操作符存储在栈中，并且，当它的右操作数处理完毕后，该操作数在栈顶. 我们知道，对于中缀表达式来说，操作符的右操作数的结束标志不唯一（有以括号为标志的，有以操作符为标志的，还有以串输入结束为标志的）. 因此需要分情形处理. 遇到括号时，有两种可能，即左括号和右括号. 如果是左括号，则表示是右操作数的开始标志，即应存入堆栈中. 如果是右括号，则应在堆栈中寻找相应的左
5、括号，并把左括号以上的操作符都弹出堆栈，加到输出序列中，当以操作符为标志时，如果该操作符的优先级不大于栈顶元素的优先级（即说明该操作符是栈顶操作符的右操作数的结束标志），则应把栈顶元素加到输出序列中；否则应该将该操作符存储到栈中（此时该操作符不是栈顶操作符的右操作数的结束标志）. 而当以串输入结束为标志时，此时我们引入符号“$”表示串输入结束，且规定“$”的优先级应低于实际操作符的优先级. 由上述分析我们能给出如下的转换算法. 例8.12 转换中缀表达式为波兰后缀表达式，中缀表达式存储在数组El: n中，相应的波兰后缀表达式存储在数组Pl: m中。算法CINNFIX（E . P） CF1初始化
6、CREATS（S）.S“#”. / “#”符号是栈底标志，当转换还没有结束时，栈永不为空j0 . / 输出序列指针i0 . / 输入串指针CF2利用栈进行转换WHILE PEEK（S）“$” DO （ ii+1 . IF ISOPD（Ei）THEN / /操作数直接输出 （jj+1 . PjEi）. IF Ei = “（” THEN SEi . /左括号压栈 IF Ei = “）” THEN / 括号匹配过程 （ xS . WHILE x “（” DO （jj+1 . Pjx . xS）IF ISOPTOR（Ei） THEN （ WHILE PREC（Ei）PREC（PEEK（S） DO （jj+1 . PjS）. SEi） 说明：（1） 算法CINFIX用符号“#”来标志栈的底部，并规定它的优先级比“$”的优先级低，该符号的作用是为了保证堆栈永不为空. （2） 子函数PEEK（S）读取S的栈顶元素值（不删除）；（3） 谓词ISOPD（P）：当P是操作数时为真，否则为假；（4） 子函数PREC定义如下： 算法CINFIX没有考虑到中缀表达式有句法错误的情况，对于实用而言，转换算法一定要给出检查句法错误的功能.