我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述三条运算规则，在运算 的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一；θ1<θ2 θ1的优先权低于θ2 θ1=\θ2 θ1的优先权等于θ2\θ1>θ2 θ1的优先权高于θ2
下表定义了算符之间的这种优先关系。
为实现算符优先算法，可以使用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作POND ，用以寄存操作数或运算结果。算法的基本思想是：
1)首先置操作数栈为空，表达式起始符\为运算栈的栈底元素；
2)依此读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶 运算符比较优先权后作相应操作，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为\。
以下算法描述了这个求值过程。 FUNC exp_reduce：operandfype； {算术表达式求值的算符优先算法。假定从终端输入的表达式无语法错误，以\作结束符。 设OPTR和OPND分别为运算符栈和操作数栈，OP为运算符的集合} INISTACK(OPTR)；PUSH(OPTR，'#')；INISTACK(OPND)；
{栈初始化，并在运算符栈的栈底压入表达式左端的虚设字符'#'} read(w)；{从终端接受一个字符}
WHILE NOT ((w='#')AND(GETTOP(OPTR)='#'))DO IF w NOT IN op THEN PUSH(OPND，w)
ELSE CASE precde(GETTOP(OPTR)，w)OF
'<'：[PUSH(OPTR，w)；read(w)]；{栈顶元素优先权低} '=\：[x：=POP(OPTR)；read(w)]；{脱括弧并接受下一字符}
\：[theta：=POP(OPTR)； b：=POP(OPND)； a：=POP(OPND)； PUSH(OPND，operate(a，theta，b))]{退栈并将运算结果入栈} ENDC；
RETURN(GETTOP(OPND)) ENDF；{exp_reducde}
算法中还调用了两个函数。其中precede是判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间优先关系的函数；orerate为进行二元运算aθb的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。
- 49 -
例：利用算法exp_reducde对算术表达式3*（7-2）求值，操作过程如下所示。
5. 栈的应用之二——递归算法的非递归实现。
栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通过一系列的过程语句间接地调用自己的过程，称做递归过程。
例如， PROCEDURE A; BEGIN ? ? ? A; ? ? ? END; 过程A中的语句A直接调用了过程A本身，这叫做直接递归调用。又如： PROCEDURE B; PROCEDURE C; BEGIN BEGIN ? ? ? ? ? ? C; C; ? ? ? ? ? ? END; END; 在过程B中调用了过程C,而过程C又调用了过程B.这两个过程都通过另一个过程调用了它们自己, 这就叫做间接调用。
递归是程序设计中一个强有力的工具。
其一,有很多数学函数是递归定义的,如大家熟悉的阶乘函数 Fact(n)=1 若n = 1 Fact(n)= n?Fact(n-1) 若n >1 2阶Fibonacci数列 Fib(n)=0 若 n=0 Fib(n)=1 若n=1 Fib(n)=Fib(n-1)+Fib(n-2) 其它情形 和Ackerman函数 Ack(m,n)=n+1 m=0 Ack(m,n)=Ack(m-1,1) n=0 Ack(m,n)=Ack(m-1,Ack(m,n-1)) 其它情形等;
其二,有的数据结构,如二叉树,广义表等,由于结构本身固有的递归特性,则它们的操作可递归地描述;
其三,还有一类问题,虽则问题本身没有明显的递归结构,但用递归求解比迭代求解更简单,如八皇后问题,Hanio塔问题等. 练习：（1998）栈S初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是______D (A){5，4，3，2，1} (B) {2，1} (C) {2，3} (D) {3，4}
五、 队列 1.队列的特点：
队列也是一种线性表，对于它所有的插入都在队列的一端进行，所有的删除都在另一端进行，进行删除的一端叫队列的“头”，进行插入的一端叫队列的“尾”，其操作特点是“先进先出”(First In First Out)表，简称FIFO表。
2.队列的一般定义：
- 50 -
相关推荐：
loading