第三章 栈和队列2

1、 限于二元运算符的表达式定义: 表达式表达式 := (操作数操作数) + (运算符运算符) + (操作数操作数) 操作数操作数 := 简单变量简单变量 | 表达式表达式 简单变量简单变量 : = 标识符标识符 | 无符号整数无符号整数 例例5 表达式求值表达式求值 表达式的三种标识方法：表达式的三种标识方法：设设 Exp = S1 OP S2则称则称 OP S1 S2 为前缀表示法前缀表示法S1 OP S2 为中缀表示法中缀表示法 S1 S2 OP 为后缀表示法后缀表示法 例：exp = a * b + ( c - d/e ) * fo前缀表达式：n + a * b (c - d/e ) *

2、fn + * ab * (c - d/e) fn + * ab * - c d/e fn + * ab * - c/ def后缀表达式o a * b (c - d/e ) * f +o a b * c - d/e f * +o a b * c d/e - f * +o a b * c d e / - f * +例如: Exp = a b + (c d / e) fo前缀式: + a b c / d e fo中缀式: a b + c d / e fo后缀式: a b c d e / f + 结论o1）操作数之间的相对次序不变o2）运算符的相对次序不同o3）中缀式丢失了括弧信息，致使运算的次序不确

3、定;o4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;o5)后缀式的运算规则为:运算符在式中出现的顺序恰为 表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式下面给出两种求表达式值的方法下面给出两种求表达式值的方法o用后缀式求表达式的值n 中缀式变为后缀式n 后缀式求值o直接从原表达式求值如何从后缀式求值如何从后缀式求值o先找运算符，再找操作数先找运算符，再找操作数例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f算法描述void value(char suffix ,int *c)

4、char *p,ch; InitStack(S); p=suffix; ch=*p; while(ch!=#) if(!IN(ch, OP) push(S,ch); else pop(S,a);pop(S,b);push(S,operate(a,ch,b) pop(S,*c);如何从原表达式求得后缀式如何从原表达式求得后缀式o分析 “原表达式” 和 “后缀式”中的运算符:n原表达式: a + b c d / e fn 后缀式: a b c + d e / f o 中缀式中每个运算符的运算次序要由它之它之后的一个运算符后的一个运算符来定；在后缀式中,优先数高的运算符领先于优先数低的运算符。从原表

5、达式求得后缀式的规律1)设立暂存运算符的栈;2) 设表达式的结束符为“#”, 予设运算符栈的栈底为“#”3) 若当前字符是操作数， 则直接发送给后缀式;4)若当前运算符的优先数高于栈顶运算符，则进栈;若当前运算符是左圆括号，则进栈；5) 若当前运算符是右圆括号， 退出栈顶运算符发送给后缀式，直至退出的栈顶运算符是左圆括号为止; 若当前运算符优先数小于等于栈顶运算符，则退出栈顶运算符发送给后缀式void transform(char suffix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty

6、(S) if (!IN(ch, OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c)&precede(c)precede(ch) Pass( Su

7、ffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / switch直接从原表达式求值直接从原表达式求值o运算规则（算符优先法）n实现算符优先法，使用两个工作栈：n运算符栈：OPTR 操作数栈：OPNDo算法基本思想：n（1）置操作数栈OPND及操作符栈OPTR为空栈。“#”置为OPTR的栈底元素。n（2）依次读入表达式中每个字符，若是操作数则进OPND，若是运算符，则进行判断： 若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹

8、出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。 若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。若读入的是“#”，且运算符栈顶的符号也是“#”时，则表达式处理结束。从操作数栈弹出表达式结果。OperandType EvaluateExpression() InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar(); While(c!=#|GetTop(OPTR)!=#)

9、 if(!In(c,OP) Push(OPND,c);c=getchar(); else /whilec=Gettop(OPND); DestroyStack(OPTR); DestroyStack(OPND); return c; if(Precede(GetTop(OPTR) Precede(c) theta = Pop(OPTR); b= Pop(OPND); a = Pop(OPND); Push(OPND,Operate(a,theta,b); 例：例：3*（7-2）步骤步骤 OPTR 栈栈 OPND栈栈 输入字符输入字符 主要操作主要操作1 # 3*(7-2)# Push(OPND

10、,3)2 # 3 *(7-2)# Push(OPTR,*)3 #* 3 (7-2)# Push(OPTR,()4 #*( 3 7-2)# Push(OPTR,7)5 #*( 37 -2)# Push(OPTR,-)6 #*(- 37 2)# Push(OPTR,2)7 #*(- 372 )# Operate(7,-,2)8 #*( 35 )# Pop(OPTR)9 #* 35 # operate(3,*,5)10 # 15 # return (GetTop(opnd)3.4 栈与递归栈与递归o 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：n将所有的实在参数

11、、返回地址等信息传递给被调用函数保存;n为被调用函数的局部变量分配存储区;n将控制转移到被调用函数的入口o从被调用函数返回返回调用函数之前之前，应该完成下列三项任务：n保存被调函数的计算结果;n释放被调函数的数据区;n依照被调函数保存的返回地址将控制转移到调用函数。多个函数嵌套调用的规则后调用先返回此时的内存管理实行“栈式管理栈式管理”void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区 为了保证递归过程正确执行为了保证递归过程正确执行( (后调用先返回后调用先返回) )，系统需设立一个

12、，系统需设立一个“递归工作栈递归工作栈”，每一层递，每一层递归所需信息构成一个归所需信息构成一个“工作记录工作记录”，（包括所，（包括所有的实参，所有的局部变量以及上一层的返回有的实参，所有的局部变量以及上一层的返回地址）。每进入一层递归，就产生一个新的工地址）。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录。弹出一个工作记录。 递归函数执行的过程可视为同一函数同一函数进行嵌套调用，例如：如何实现递归调用如何实现递归调用栈顶：递归工作记录n递归工作记录2栈底：递归工作记录1递归工作记录的数递归工作记录的数据有：据

13、有：上一层函数调用的上一层函数调用的返回地址、实参表返回地址、实参表、局部变量、局部变量。 递归工作栈递归工作栈以求4的阶乘为例：fac(4)=4*fac( 3)fac(3)=3*fac( 2)fac(2)=2*fac(1)fac(3)=3*2*1fac(4)=4*3*2*1下下推推回回代代fac(1)=1fac(2)=2*1oint Fac( int n)o o1 int s;o2 if ( n=1) s=1;o3 else s=n*Fac(n-1);o4 return(s);o main()int s = Fac(4);00，43，33，23，1void hanoi (int n, cha

14、r x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从x移到z3 else 4 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔5 move(x, n, z); / 将编号为n的圆盘从x移到z6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔7 8 8 3 a b c返址 n x y z5 2 a c b5 1 a b cvoid hanoi (int n, char x, char y, char z) 1 if (n=1)2 move(x, 1, z); 3 else 4 hanoi(n-1, x, z, y); 5 move(x, n, z); 6 hanoi(n-1, y, x, z); 7 8 7 1 c a b练习：例1:依次打印输出自然数1到n的递归过程。void WRT(int n) if (n!=0) WRT(n-1); printf(%d, n);例2、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s) int