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