第三章 栈和队列2

限于二元运算符的表达式定义:

表达式::=(操作数)+(运算符)+(操作数)

操作数::=简单变量|表达式简单变量::=标识符|无符号整数

例5表达式求值

表达式的三种标识方法：设

Exp=S1

OP

S2则称

OP

S1

S2

为前缀表示法S1

OP

S2

为中缀表示法

S1

S2

OP

为后缀表示法

例：exp=a*b+(c-d/e)*f前缀表达式：

+{a*b}{(c-d/e)*f}+*ab*{(c-d/e)}f+*ab*-c{d/e}f+*ab*-c/def后缀表达式

{a*b}{(c-d/e)*f}+ab*{c-d/e}f*+ab*c{d/e}-f*+ab*cde/-f*+例如:Exp=ab

+

(cd/e)f前缀式:+

ab

c/def中缀式:ab

+

cd/ef后缀式:ab

cde/f

+

结论1）操作数之间的相对次序不变2）运算符的相对次序不同3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式下面给出两种求表达式值的方法用后缀式求表达式的值中缀式变为后缀式后缀式求值直接从原表达式求值如何从后缀式求值先找运算符，再找操作数例如：

abcde/f+abd/ec-d/e(c-d/e)f算法描述voidvalue(charsuffix[],int*c){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);}如何从原表达式求得后缀式分析“原表达式”和“后缀式”中的运算符:原表达式:a+b

cd/e

f

后缀式:abc+de/f

中缀式中每个运算符的运算次序要由它之后的一个运算符来定；在后缀式中,优先数高的运算符领先于优先数低的运算符。从原表达式求得后缀式的规律设立暂存运算符的栈;

设表达式的结束符为“#”,予设运算符栈的栈底为“#”3)若当前字符是操作数，则直接发送给后缀式;若当前运算符的优先数高于栈顶运算符，则进栈;若当前运算符是左圆括号，则进栈；5)若当前运算符是右圆括号，退出栈顶运算符发送给后缀式，直至退出的栈顶运算符是左圆括号为止;若当前运算符优先数小于等于栈顶运算符，则退出栈顶运算符发送给后缀式voidtransform(charsuffix[],charexp[]){

InitStack(S);Push(S,#);p=exp;ch=*p;while(!StackEmpty(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(Suffix,c);Pop(S,c);}

if(ch!=

#)Push(S,ch);

break;

}//switch直接从原表达式求值运算规则（算符优先法）实现算符优先法，使用两个工作栈：运算符栈：OPTR操作数栈：OPND算法基本思想：（1）置操作数栈OPND及操作符栈OPTR为空栈。“#”置为OPTR的栈底元素。（2）依次读入表达式中每个字符，若是操作数则进OPND，若是运算符，则进行判断：若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。若读入的是“#”，且运算符栈顶的符号也是“#”时，则表达式处理结束。从操作数栈弹出表达式结果。OperandType

EvaluateExpression(){

InitStack(OPTR);Push(OPTR,'#');

InitStack(OPND);c=getchar();

While(c!=‘#’||GetTop(OPTR)!=‘#’){

if(!In(c,OP)){Push(OPND,c);c=getchar();}

else{…}}//whilec=Gettop(OPND);DestroyStack(OPTR);DestroyStack(OPND);returnc;}if(Precede(GetTop(OPTR))<Precede(c)||c==‘(’){Push(OPTR,c);c=getchar();}elseif((Precede(GetTop(OPTR))==Precede(c)){x=Pop(OPTR);c=getchar();}elseif((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栈输入字符主要操作

#

3*(7-2)#Push(OPND,’3’)#3*(7-2)#Push(OPTR,’*’)#*3

(7-2)#Push(OPTR,’(’)#*(3

7-2)#Push(OPTR,’7’)#*(37-2)#Push(OPTR,’-’)#*(-372)#Push(OPTR,’2’)#*(-372)#Operate(‘7’,’-’,’2’)#*(35

)#Pop(OPTR)#*35

#operate(‘3’,’*’,’5’)#15#return(GetTop(opnd))3.4栈与递归当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，

需先完成三项任务：将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。多个函数嵌套调用的规则后调用先返回此时的内存管理实行“栈式管理”voidmain(){voida(){voidb(){

………a();b();

……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区

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

上一层函数调用的返回地址、实参表、局部变量。

递归工作栈以求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*1int

Fac(intn){1ints;2if(n==1)s=1;3elses=n*Fac(n-1);4return(s);}main(){ints=Fac(4);0}0，43，33，23，1voidhanoi(intn,charx,chary,charz){//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1if(n==1)2move(x,1,z);//将编号为１的圆盘从x移到z3else{4hanoi(n-1,x,z,y);//将x上编号为１至n-1的

//圆盘移到y,z作辅助塔5move(x,n,z);//将编号为n的圆盘从x移到z6hanoi(n-1,y,x,z);//将y上编号为１至n-1的

//圆盘移到z,x作辅助塔7}8}83abc返址nxyz52acb51abcvoidhanoi(intn,