第三章 棧和隊列2

限于二元運算符的表達式定義:

表達式::=(操作數(shù))+(運算符)+(操作數(shù))

操作數(shù)::=簡單變量|表達式簡單變量::=標識符|無符號整數(shù)

例5表達式求值

表達式的三種標識方法：設(shè)

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

+

結(jié)論1）操作數(shù)之間的相對次序不變2）運算符的相對次序不同3）中綴式丟失了括弧信息，致使運算的次序不確定;4)前綴式的運算規(guī)則為:連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一個最小表達式;5)后綴式的運算規(guī)則為:運算符在式中出現(xiàn)的順序恰為表達式的運算順序;每個運算符和在它之前出現(xiàn)且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達式下面給出兩種求表達式值的方法用后綴式求表達式的值中綴式變?yōu)楹缶Y式后綴式求值直接從原表達式求值如何從后綴式求值先找運算符，再找操作數(shù)例如：

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

中綴式中每個運算符的運算次序要由它之后的一個運算符來定；在后綴式中,優(yōu)先數(shù)高的運算符領(lǐng)先于優(yōu)先數(shù)低的運算符。從原表達式求得后綴式的規(guī)律設(shè)立暫存運算符的棧;

設(shè)表達式的結(jié)束符為“#”,予設(shè)運算符棧的棧底為“#”3)若當前字符是操作數(shù)，則直接發(fā)送給后綴式;若當前運算符的優(yōu)先數(shù)高于棧頂運算符，則進棧;若當前運算符是左圓括號，則進棧；5)若當前運算符是右圓括號，退出棧頂運算符發(fā)送給后綴式，直至退出的棧頂運算符是左圓括號為止;若當前運算符優(yōu)先數(shù)小于等于棧頂運算符，則退出棧頂運算符發(fā)送給后綴式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直接從原表達式求值運算規(guī)則（算符優(yōu)先法）實現(xiàn)算符優(yōu)先法，使用兩個工作棧：運算符棧：OPTR操作數(shù)棧：OPND算法基本思想：（1）置操作數(shù)棧OPND及操作符棧OPTR為空棧?！?”置為OPTR的棧底元素。（2）依次讀入表達式中每個字符，若是操作數(shù)則進OPND，若是運算符，則進行判斷：若是“（”，進運算符棧；若是“）”，當運算符棧頂是“（”，則彈出棧頂元素，繼續(xù)掃描下一符號。否則當前讀入符號暫不處理，從操作數(shù)棧彈出兩個操作數(shù)，從運算符棧彈出一個運算符，生成運算指令，結(jié)果送入操作數(shù)棧，繼續(xù)處理當前讀入符號。若讀入的運算符的優(yōu)先級大于運算符棧頂?shù)膬?yōu)先級，則進運算符棧，繼續(xù)掃描下一符號；否則從操作數(shù)棧頂彈出兩個操作數(shù)，從運算符棧彈出一個運算符，生成運算指令，把結(jié)果送入操作數(shù)棧。繼續(xù)處理剛才讀入的符號。若讀入的是“#”，且運算符棧頂?shù)姆栆彩恰?”時，則表達式處理結(jié)束。從操作數(shù)棧彈出表達式結(jié)果。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棧與遞歸當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，

需先完成三項任務(wù)：將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變量分配存儲區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項任務(wù)：保存被調(diào)函數(shù)的計算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個函數(shù)嵌套調(diào)用的規(guī)則后調(diào)用先返回此時的內(nèi)存管理實行“棧式管理”voidmain(){voida(){voidb(){

………a();b();

……}//main}//a}//bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)

為了保證遞歸過程正確執(zhí)行(后調(diào)用先返回)，系統(tǒng)需設(shè)立一個“遞歸工作棧”，每一層遞歸所需信息構(gòu)成一個“工作記錄”，（包括所有的實參，所有的局部變量以及上一層的返回地址）。每進入一層遞歸，就產(chǎn)生一個新的工作記錄壓入棧頂。每退出一層遞歸，就從棧頂彈出一個工作記錄。遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進行嵌套調(diào)用，例如：如何實現(xiàn)遞歸調(diào)用棧頂：遞歸工作記錄n……遞歸工作記錄2棧底：遞歸工作記錄1遞歸工作記錄的數(shù)據(jù)有：

上一層函數(shù)調(diào)用的返回地址、實參表、局部變量。

遞歸工作棧以求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個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1if(n==1)2move(x,1,z);//將編號為１的圓盤從x移到z3else{4hanoi(n-1,x,z,y);//將x上編號為１至n-1的

//圓盤移到y(tǒng),z作輔助塔5move(x,n,z);//將編號為n的圓盤從x移到z6hanoi(n-1,y,x,z);//將y上編號為１至n-1的

//圓盤移到z,x作輔助塔7}8}83abc返址nxyz52acb51abcvoidhanoi(intn,