第四章棧的應(yīng)用

1、4.1.5 4.1.5 棧的應(yīng)用舉例棧的應(yīng)用舉例例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)4.2 4.2 表達(dá)式求值表達(dá)式求值4.3.4.3.遞歸遞歸例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換算法基于原理：算法基于原理： N = (N div d)d + N mod d 例如：例如：（1348)10 = (2504)8 ，其運(yùn)算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計(jì)算順序計(jì)算順序輸出順序輸出順序 void Transform(long num, int r) Stack a; InitStack(a)

2、; /初始化棧初始化棧 while(num!=0) int k=num % r; Push(a,k); /計(jì)算順序進(jìn)棧計(jì)算順序進(jìn)棧 num/=r; while(!StackEmpty(a) /出棧出棧 coutPop(a); coutendl; 例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中假設(shè)在表達(dá)式中（）（）或或（ ）等為正確的格式，等為正確的格式，（ ）或（）或（ ）或或 （）（）)均為不正確的格式。均為不正確的格式。則 檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。分析可能出現(xiàn)的不匹配不匹配的情況: : 到來的右括弧到來的右括弧并非是所并非是所“期待期待”的；的

3、；例如：考慮下列括號(hào)序列：例如：考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8 到來的是“不速之客”； 直到結(jié)束，也沒有到來所“期待”的括弧。 算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想： 1 1）左括弧左括弧: : 則進(jìn)棧則進(jìn)棧 2 2）出現(xiàn)）出現(xiàn)右括弧右括弧: : 若棧空，若棧空，不匹配不匹配。 否則和棧頂元素比較，否則和棧頂元素比較， 若相匹配，則若相匹配，則“左括弧出棧左括弧出?！?” ， 否則表明否則表明不匹配不匹配。 3 3）表達(dá)式檢驗(yàn)）表達(dá)式檢驗(yàn)結(jié)束結(jié)束時(shí)，時(shí)， 若若棧空?？眨磉_(dá)式中匹配，表達(dá)式中匹配正確正確， 否則否則不匹配不匹配。 switch (ch) case : ca

4、se (: Push(a,ch); break; /左括號(hào)進(jìn)棧左括號(hào)進(jìn)棧 case : if(Peek(a)=) Pop(a); /右括號(hào)右括號(hào) else return 0; break; if(StackEmpty(a) return 1; else return 0; 二元運(yùn)算符的表達(dá)式定義二元運(yùn)算符的表達(dá)式定義: : 表達(dá)式表達(dá)式:=(:=(操作數(shù)操作數(shù))+()+(運(yùn)算符運(yùn)算符)+()+(操作數(shù)操作數(shù)) ) 操作數(shù)操作數(shù):=:=簡(jiǎn)單變量簡(jiǎn)單變量 | | 表達(dá)式表達(dá)式 簡(jiǎn)單變量簡(jiǎn)單變量:=:=標(biāo)識(shí)符標(biāo)識(shí)符 | | 無符號(hào)整數(shù)無符號(hào)整數(shù)4.2 4.2 表達(dá)式求值表達(dá)式求值 表達(dá)式的三種標(biāo)識(shí)方

5、法：表達(dá)式的三種標(biāo)識(shí)方法：設(shè)設(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中綴式: a b + c d / e f后綴式: a b c d e / f + 結(jié)論結(jié)論: :1 1）操作數(shù)之間的相對(duì)次序）操作數(shù)之間的相對(duì)次序不變不變; ;2 2）運(yùn)算符的相對(duì)次序）運(yùn)算符的相對(duì)次序不同不同; ;4)4)前綴式前綴式連續(xù)出現(xiàn)的兩個(gè)操作數(shù)連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在

6、它們之前且緊靠它們的運(yùn)算和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式符構(gòu)成一個(gè)最小表達(dá)式; ;3)3)中綴式中綴式丟失了括弧信息，丟失了括弧信息， 致使運(yùn)算的次序致使運(yùn)算的次序不確定不確定;5)5)后綴式后綴式算符在式中出現(xiàn)的順序算符在式中出現(xiàn)的順序恰為恰為表達(dá)式的運(yùn)算順序表達(dá)式的運(yùn)算順序; ;每個(gè)運(yùn)算每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式。個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式。中綴式轉(zhuǎn)換為后綴式中綴式轉(zhuǎn)換為后綴式: :1. 3/5+6 3 5 / 6 +2. 16-9*(4+3) 16 9 4 3 + * -3. 2*(x+y)/(1-x) 2

7、x y + * 1 x - /4. (25 + x) * (a * (a+b) +b)25 x +aa b +*b +*如何從后綴式求值？如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)先找運(yùn)算符，再找操作數(shù)例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f(a b)+(c-d/e) f char a30=12 3 20 4 / * 8 - 6 * +;4/5*1587-6*42+54 while(ch!=) /掃描每一個(gè)字符掃描每一個(gè)字符 switch(ch) case *: x=Pop(S)*Pop(S); break; case /: x=Pop(S); / 彈

8、出除數(shù)彈出除數(shù) if(x!=0.0) x=Pop(S)/x; /彈出的是被除數(shù)彈出的是被除數(shù) else cerrDiv by 0!x; /讀入一個(gè)浮點(diǎn)數(shù)讀入一個(gè)浮點(diǎn)數(shù) Push(S,x); /浮點(diǎn)數(shù)或運(yùn)算的結(jié)果壓棧浮點(diǎn)數(shù)或運(yùn)算的結(jié)果壓棧 insch; /輸入下一個(gè)字符輸入下一個(gè)字符 如何從中綴表達(dá)式求得后綴式？如何從中綴表達(dá)式求得后綴式？在中綴式中，每個(gè)運(yùn)算符的運(yùn)算次序要由它它后一個(gè)后一個(gè)運(yùn)算符運(yùn)算符來定，在后綴式中，運(yùn)算符按實(shí)際運(yùn)算次序排列。表達(dá)式: : a + b c d / e f 后綴式: : a b c + d e / f 從中綴式求得后綴式的算法為：從中綴式求得后綴式的算法為：1)

9、 設(shè)立操作符棧棧R R；運(yùn)算符優(yōu)先級(jí)運(yùn)算符優(yōu)先級(jí) 高于棧頂則入棧高于棧頂則入棧; ; 否則，否則，出棧出棧發(fā)發(fā)給后綴式給后綴式S2S2中；直到高于棧頂則中；直到高于棧頂則入棧入棧2) 設(shè)表達(dá)式的結(jié)束符為“”， 預(yù)設(shè)運(yùn)算符棧R的棧底為“”；3) 若當(dāng)前字符是操作數(shù)， 則直接發(fā)送給后綴式S2中。4)4)“(”“(” 直接直接進(jìn)棧進(jìn)棧; ;優(yōu)先級(jí)最低優(yōu)先級(jí)最低“0 0” “)” “)”R R中運(yùn)算符中運(yùn)算符出棧出棧, , 直到遇到直到遇到 左括弧左括弧“(”(” 為止。為止。 字符串字符串S1=10+(18+9*3)/15-6 棧棧R R暫存運(yùn)算符暫存運(yùn)算符S2存放轉(zhuǎn)換后的后綴式字符串字符串1 0+

10、(1 8+9*3)*+/1 5-/ +- 保存保存被調(diào)函數(shù)的被調(diào)函數(shù)的計(jì)算結(jié)果計(jì)算結(jié)果； 釋放釋放被調(diào)函數(shù)的被調(diào)函數(shù)的數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)； 依照被調(diào)函數(shù)保存的返回地址將依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移控制轉(zhuǎn)移到主調(diào)函數(shù)。到主調(diào)函數(shù)。從被調(diào)用函數(shù)從被調(diào)用函數(shù)返回返回主調(diào)用函數(shù)主調(diào)用函數(shù)之前之前，應(yīng)該完成下列三項(xiàng)任務(wù)：應(yīng)該完成下列三項(xiàng)任務(wù)：多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：內(nèi)存管理實(shí)行內(nèi)存管理實(shí)行“棧式管理?xiàng)Ｊ焦芾怼焙笳{(diào)用先返回后調(diào)用先返回 ！main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)函數(shù)函數(shù)a

11、的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)函數(shù)函數(shù)b的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū) 函數(shù)函數(shù)f(n)=n!，遞歸函數(shù)遞歸函數(shù)f f(n)可表示為可表示為 1 (n=0) f(n)= n*f(n-1) (n0)遞歸函數(shù)執(zhí)行的過程可視為同一同一函數(shù)函數(shù)進(jìn)行嵌套調(diào)用，例如： 求解求解 f(n)=n! 的遞歸函數(shù)為：的遞歸函數(shù)為： long f(int n) if(n=0) return 1; else return n*f(n-1); 求求f(4)=4! 遞歸表示遞歸表示: n*f(n-1) 結(jié)束條件結(jié)束條件 f(0)=0!=14 r13 r22 r21 r20 r2計(jì)算計(jì)算f(4)= 4*f(4-1) 計(jì)算計(jì)算f(3)= 3*f(3-1

12、) 計(jì)算計(jì)算f(2)= 2*f(2-1)計(jì)算計(jì)算f(1)= 1*f(1-1)計(jì)算計(jì)算f(0)= 1126244.1.5 4.1.5 棧的應(yīng)用舉例棧的應(yīng)用舉例例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)4.2 4.2 表達(dá)式求值表達(dá)式求值4.3.4.3.遞歸遞歸 一個(gè)無頭結(jié)點(diǎn)單鏈表按逆序輸出：一個(gè)無頭結(jié)點(diǎn)單鏈表按逆序輸出： void verout(LNode *L) while L verout(L-next); coutdata; void delete(LinkList &L, ElemType x) / L為無頭結(jié)點(diǎn)的單鏈表的頭指針為無頭結(jié)點(diǎn)的單鏈表的頭

13、指針if (L) if (L-data=x) p=L; L=L-next; free(p); delete(L, x); else delete(L-next, x); 1. 實(shí)現(xiàn)遞歸函數(shù)，必須利用“棧”。一個(gè)遞歸遞歸函數(shù)必定能改寫改寫為利用棧實(shí)現(xiàn)的非遞歸函數(shù)；反之，一個(gè)用棧實(shí)現(xiàn)的非遞歸函數(shù)可以改寫為遞歸函數(shù)。需要注意的是遞歸函數(shù)遞歸層次的深度決定所需存儲(chǔ)量的大小。2.2. 分析遞歸算法的工具是分析遞歸算法的工具是遞歸樹遞歸樹. 從遞歸樹上可以得到遞歸函數(shù)的各種從遞歸樹上可以得到遞歸函數(shù)的各種 相關(guān)信息。相關(guān)信息。遞歸遞歸樹的深度樹的深度即為遞歸即為遞歸 函數(shù)的函數(shù)的遞歸深度遞歸深度； 遞歸樹

14、上的遞歸樹上的結(jié)點(diǎn)數(shù)目結(jié)點(diǎn)數(shù)目恰為函數(shù)中的恰為函數(shù)中的 主要操作主要操作重復(fù)次數(shù)重復(fù)次數(shù) 例如例如: : n=3的梵塔算法中主要操作的梵塔算法中主要操作 move的執(zhí)行次數(shù)遞歸樹的執(zhí)行次數(shù)遞歸樹: :move(3, a, b, c)move(2, a, c, b)move(2, b, a, c)move(1, a, b, c)move(1, c, a, b)move(1, b, c, a)move(1, a, b, c)4.3 4.3 棧與遞歸棧與遞歸 將所有的實(shí)在參數(shù)、返回地址等將所有的實(shí)在參數(shù)、返回地址等信息信息傳遞給被調(diào)函數(shù)傳遞給被調(diào)函數(shù)保存保存； 為被調(diào)函數(shù)的局部變量為被調(diào)函數(shù)的局部變

15、量分配存儲(chǔ)區(qū)分配存儲(chǔ)區(qū) 將將控制轉(zhuǎn)移控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。到被調(diào)用函數(shù)的入口。 一個(gè)主調(diào)函數(shù)，在一個(gè)主調(diào)函數(shù)，在運(yùn)行被調(diào)用函運(yùn)行被調(diào)用函數(shù)之前數(shù)之前，需先完成三項(xiàng)任務(wù)：，需先完成三項(xiàng)任務(wù)：3.3.若遞歸樹若遞歸樹蛻化蛻化為為單支樹或者遞歸樹單支樹或者遞歸樹中含有很多中含有很多相同相同的結(jié)點(diǎn)，則表明該的結(jié)點(diǎn)，則表明該遞歸函數(shù)遞歸函數(shù)不適用不適用。nn-110。計(jì)算斐波那契遞歸函數(shù)的遞歸樹中計(jì)算斐波那契遞歸函數(shù)的遞歸樹中有很多有很多重復(fù)重復(fù)出現(xiàn)的結(jié)點(diǎn)。出現(xiàn)的結(jié)點(diǎn)。F5F4F3F3F2F2F1F1F0F1F0。4. 遞歸函數(shù)中的遞歸函數(shù)中的尾遞歸尾遞歸容易容易消除消除。例如：先序遍歷二叉樹可以改寫為：例如：先序遍歷二叉樹可以改寫為： void PreTraverse( BiTree T) While (T) Visit(T-data); PreTraverse(T-lchild); T = T-rchild; / PreTraversevoid delete(LinkList &L, ElemType x) / L為無頭結(jié)點(diǎn)的單鏈表的頭指針為無頭結(jié)點(diǎn)的單鏈表的頭指針if (L) if (L-dat