數(shù)據(jù)結(jié)構(gòu)第三章 棧和隊(duì)列part2)

1、3.3 3.3 棧的應(yīng)用舉例棧的應(yīng)用舉例例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)例三、例三、 行編輯程序問(wèn)題行編輯程序問(wèn)題例四、例四、 迷宮求解迷宮求解例五、例五、 表達(dá)式求值表達(dá)式求值例七、例七、 實(shí)現(xiàn)遞歸實(shí)現(xiàn)遞歸例六、例六、 二元運(yùn)算符的表達(dá)式的標(biāo)識(shí)二元運(yùn)算符的表達(dá)式的標(biāo)識(shí) 例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d)d + N mod d 例如：例如：（1348)10 = (2504)8 ，其運(yùn)算過(guò)程如下：其運(yùn)算過(guò)程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計(jì)算

2、順序計(jì)算順序輸出順序輸出順序void conversion ( ) InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn) 假設(shè)在表達(dá)式中假設(shè)在表達(dá)式中 （）或（）或（ ） 等為正確的格式，等為正確的格式， （ ）或（）或（ ）或）或 （）（）) ) 均為不正確的格式。均為不正確的格式。則則 檢驗(yàn)括號(hào)是否匹配檢驗(yàn)括號(hào)是否匹配的方法可用的方法可用“期待的急迫程度

3、期待的急迫程度”這個(gè)概念來(lái)描述。這個(gè)概念來(lái)描述。分析可能出現(xiàn)的分析可能出現(xiàn)的不匹配不匹配的情況的情況: 到來(lái)的右括弧到來(lái)的右括弧并非是所并非是所“期待期待”的；的；例如：考慮下列括號(hào)序列：例如：考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8 到來(lái)的是到來(lái)的是“不速之客不速之客”； 直到結(jié)束，也沒(méi)有到來(lái)直到結(jié)束，也沒(méi)有到來(lái)所所“期待期待”的括的括弧?；?。算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想：1 1)凡出現(xiàn)左括弧左括弧，則進(jìn)棧進(jìn)棧；2 2)凡出現(xiàn)右括弧右括弧，首先檢查棧是否空 若棧空?？眨瑒t表明該“右括弧右括弧”多余多余， 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧

4、出?！?” ， 否則表明不匹配不匹配。3 3)表達(dá)式表達(dá)式檢驗(yàn)結(jié)束結(jié)束時(shí)， 若?？諚？?，則表明表達(dá)式中匹配正確匹配正確， 否則表明“左括弧左括弧”有余有余。Status matching(string& exp) int state = 1; while (i=Length(exp) & state) switch of expi case “(”:“(”:Push(S,expi); i+; break; case”)”: if(NOT StackEmpty(S)&GetTop(S)=“(“ Pop(S,e); i+; else state = 0; break; if

5、 (StackEmpty(S)&state) return OK; .例三、行編輯程序問(wèn)題例三、行編輯程序問(wèn)題 一個(gè)簡(jiǎn)單的行編輯程序的功能是：接收用戶從一個(gè)簡(jiǎn)單的行編輯程序的功能是：接收用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。 由于用戶在終端上進(jìn)行輸入時(shí)，不能保證不出由于用戶在終端上進(jìn)行輸入時(shí)，不能保證不出差錯(cuò)，因此，若在編輯程序中，差錯(cuò)，因此，若在編輯程序中，“每接收一個(gè)字符每接收一個(gè)字符即存入用戶數(shù)據(jù)區(qū)即存入用戶數(shù)據(jù)區(qū)”的做法顯然不是最恰當(dāng)?shù)?。的做法顯然不是最恰當(dāng)?shù)摹?設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入設(shè)立一個(gè)輸入緩沖區(qū)，用以接受

6、用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)設(shè)“#”為退格符，為退格符，“”為退行符。為退行符。合理的作法是：合理的作法是：假設(shè)從終端接受了這樣兩行字符：假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);則實(shí)際有效的是下列兩行：則實(shí)際有效的是下列兩行： while (*s) putchar(*s+); 為此，可設(shè)這個(gè)輸入緩沖區(qū)為一個(gè)棧結(jié)構(gòu)，為此，可設(shè)這個(gè)輸入緩沖區(qū)為一個(gè)棧結(jié)構(gòu)，每當(dāng)從終端接收了一個(gè)字符之后先作如下判別：每當(dāng)從終端接收了一個(gè)字符之后先作如下判別： 如果它既不是退格符也不是退行符

7、，則將如果它既不是退格符也不是退行符，則將 該字符壓入棧頂；該字符壓入棧頂； 如是一個(gè)退格符，則從棧頂刪去一個(gè)字符；如是一個(gè)退格符，則從棧頂刪去一個(gè)字符； 如果他是一個(gè)退行符，則將字符棧清為空棧。如果他是一個(gè)退行符，則將字符棧清為空棧?？捎孟率鏊惴▉?lái)描述：可用下述算法來(lái)描述： while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break; / 重置重置S為空棧為空棧 default : Push(S, ch); break; ch = getchar(); /

8、 從終端接收下一個(gè)字符從終端接收下一個(gè)字符 ClearStack(S); / 重置重置S為空棧為空棧 if (ch != EOF) ch = getchar();while (ch != EOF) / EOF為全文結(jié)束符為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；void LineEdit( ) InitStack(S); /構(gòu)造空棧構(gòu)造空棧 ch=getchar( ); /從終端接收第一個(gè)字符從終端接收第一個(gè)字符 while (ch!=EOF) /EOFEOF是全文結(jié)束符是全文結(jié)束符 while (ch!=EOF & ch!=n)

9、 switch (ch) case #: Pop(S,c); break; case :ClearStack(S);break; /重置重置S S為空棧為空棧 default: Push(S,ch); break; ch=getchar( ); /從終端接收下一個(gè)字符從終端接收下一個(gè)字符 將從棧底至棧頂?shù)臈?nèi)字符傳送至調(diào)用過(guò)程的數(shù)據(jù)區(qū)；將從棧底至棧頂?shù)臈?nèi)字符傳送至調(diào)用過(guò)程的數(shù)據(jù)區(qū)； ClearStack (S); /重置重置S S為空棧為空棧 if (ch!=EOF) ch=getchar( ); DestroyStack(S); /棧棧S S被銷毀被銷毀 /LineEdit例四、例四、 迷

10、宮求解迷宮求解通常用的是“窮舉求解窮舉求解”的方法# # # # # # # # # # # # $ $ $ # # # # $ $ $ # # # $ $ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 求迷宮路徑算法的基本思想基本思想是： 若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼，則納入路徑，繼續(xù)前進(jìn)續(xù)前進(jìn); 若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后退，換方，則后退，換方向繼續(xù)探索向繼續(xù)探索; 若四周若四周“均無(wú)通路均無(wú)通路”，則將當(dāng)前位置從，則將當(dāng)前位置從路徑中刪除出去。路徑中刪

11、除出去。設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通若當(dāng)前位置可通， 則則將當(dāng)前位置插入棧頂插入棧頂； 若若該位置是出口位置，則則算法結(jié)束； 否則切換否則切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置； 否則否則 while (棧不空）棧不空）；求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法： 若若棧不空且棧頂位置尚有其他方向未被探索棧不空且棧頂位置尚有其他方向未被探索，則則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針?lè)较蛐D(zhuǎn) 找到的棧頂位置的下一相鄰塊棧頂位置的下一相鄰塊；若若棧不空但棧頂位置的四周均不可通棧不空但棧頂位置的四周均不可通，則則刪去棧頂位置；/ 從路徑中刪去該通道

12、塊 若若棧不空，則則重新測(cè)試新的棧頂位置， 直至直至找到一個(gè)可通的相鄰塊或出棧至棧空； 若若棧空?？?，則則表明迷宮沒(méi)有通路。 表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯中的一個(gè)基本表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯中的一個(gè)基本問(wèn)題，它的實(shí)現(xiàn)是棧應(yīng)用的又一個(gè)典型例子。這里介問(wèn)題，它的實(shí)現(xiàn)是棧應(yīng)用的又一個(gè)典型例子。這里介紹一種簡(jiǎn)單直觀，廣為使用的算法，叫紹一種簡(jiǎn)單直觀，廣為使用的算法，叫“算符優(yōu)先算符優(yōu)先法法”。它是根據(jù)運(yùn)算優(yōu)先關(guān)系的規(guī)定來(lái)實(shí)現(xiàn)對(duì)表達(dá)式。它是根據(jù)運(yùn)算優(yōu)先關(guān)系的規(guī)定來(lái)實(shí)現(xiàn)對(duì)表達(dá)式的編譯或解釋執(zhí)行的。的編譯或解釋執(zhí)行的。例如：要對(duì)算術(shù)表達(dá)式例如：要對(duì)算術(shù)表達(dá)式 4+2*3-10/5 求值。求值。算術(shù)四則運(yùn)

13、算規(guī)則：算術(shù)四則運(yùn)算規(guī)則： 先乘除，后加減；先乘除，后加減； 同級(jí)運(yùn)算從左算到右；同級(jí)運(yùn)算從左算到右； 先括號(hào)內(nèi)，后括號(hào)外。先括號(hào)內(nèi)，后括號(hào)外。 “算符優(yōu)先法算符優(yōu)先法”就是根據(jù)這個(gè)運(yùn)算優(yōu)先關(guān)系的規(guī)就是根據(jù)這個(gè)運(yùn)算優(yōu)先關(guān)系的規(guī)定來(lái)實(shí)現(xiàn)對(duì)表達(dá)式的編譯或解釋執(zhí)行的。定來(lái)實(shí)現(xiàn)對(duì)表達(dá)式的編譯或解釋執(zhí)行的。例五、例五、 表達(dá)式求值表達(dá)式求值表達(dá)式表達(dá)式操作數(shù)操作數(shù)(operand)：常數(shù)、變量或常量標(biāo)識(shí)符：常數(shù)、變量或常量標(biāo)識(shí)符運(yùn)算符運(yùn)算符(operator)：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、 邏輯運(yùn)算符等邏輯運(yùn)算符等界限符界限符(delimiter)：（ 、）、表達(dá)式結(jié)束符等、）、表

14、達(dá)式結(jié)束符等 為了敘述的簡(jiǎn)潔，我們僅討論為了敘述的簡(jiǎn)潔，我們僅討論簡(jiǎn)單算術(shù)表達(dá)式簡(jiǎn)單算術(shù)表達(dá)式的求值問(wèn)題的求值問(wèn)題，這種表達(dá)式僅包含加、減、乘、除、，這種表達(dá)式僅包含加、減、乘、除、括號(hào)等四種運(yùn)算。不難將它推廣到更一般的表達(dá)式括號(hào)等四種運(yùn)算。不難將它推廣到更一般的表達(dá)式上。上。 我們把運(yùn)算符和界限符統(tǒng)稱為算符，它們構(gòu)成的我們把運(yùn)算符和界限符統(tǒng)稱為算符，它們構(gòu)成的集合命名為集合命名為op，在運(yùn)算的每一步中，任意兩個(gè)相繼出，在運(yùn)算的每一步中，任意兩個(gè)相繼出現(xiàn)的運(yùn)算符現(xiàn)的運(yùn)算符1和和2之間的優(yōu)先關(guān)系至多是下面三種關(guān)之間的優(yōu)先關(guān)系至多是下面三種關(guān)系之一：系之一： 1 2 : 1的優(yōu)先權(quán)高于的優(yōu)先權(quán)高于

15、2；下表定義了算符之間的這種優(yōu)先關(guān)系。下表定義了算符之間的這種優(yōu)先關(guān)系。算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表 + - * / （ ） # =+-*/()# 為實(shí)現(xiàn)算符優(yōu)先算法可使用兩個(gè)工作棧：為實(shí)現(xiàn)算符優(yōu)先算法可使用兩個(gè)工作棧： OPTROPTR棧：用以寄存運(yùn)算符；棧：用以寄存運(yùn)算符； OPNDOPND棧：用以寄存操作數(shù)或運(yùn)算結(jié)果；棧：用以寄存操作數(shù)或運(yùn)算結(jié)果；算法基本思想：算法基本思想： 首先置操作數(shù)棧為空棧，表達(dá)式起始符首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”#”為運(yùn)算符棧的棧底元素；為運(yùn)算符棧的棧底元素； 依次讀入表達(dá)式中的每個(gè)字符，若是操作依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)，則進(jìn)數(shù)，則進(jìn)O

16、PNDOPND棧；若是運(yùn)算符，則和棧；若是運(yùn)算符，則和OPTROPTR棧的棧頂棧的棧頂運(yùn)算符比較優(yōu)先數(shù)后作相應(yīng)操作，直至整個(gè)表達(dá)式運(yùn)算符比較優(yōu)先數(shù)后作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢（即求值完畢（即OPTROPTR棧的棧頂元素和當(dāng)前讀入的字符棧的棧頂元素和當(dāng)前讀入的字符均為均為“#”)#”)。OperandType EvaluateExpression( ) InitStack(OPTR); Push (OPTR,#); InitStack(OPND); c=getchar( ); while (c!=# | GetTop(OPTR)!=#) if (!In(c,OP) Push (OPND,

17、c);c=getchar( ); /操作數(shù)進(jìn)棧操作數(shù)進(jìn)棧 else switch (Precede(GetTop(OPTR),c) case : theta =Pop(OPTR); b= Pop(OPND); a=Pop(OPND); Push(OPND,Operate(a,theta,b); break; /退棧并將運(yùn)算結(jié)果入棧退棧并將運(yùn)算結(jié)果入棧 /switch /while return GetTop(OPND); / EvaluateExpression 表達(dá)式表達(dá)式 := (操作數(shù)操作數(shù)) + (運(yùn)算符運(yùn)算符) + (操作數(shù)操作數(shù)) 操作數(shù)操作數(shù) := 簡(jiǎn)單變量簡(jiǎn)單變量 | 表達(dá)式表

18、達(dá)式 簡(jiǎn)單變量簡(jiǎn)單變量 :=標(biāo)識(shí)符標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù)例六、例六、二元運(yùn)算符的表達(dá)式的標(biāo)識(shí)二元運(yùn)算符的表達(dá)式的標(biāo)識(shí) 表達(dá)式的三種標(biāo)識(shí)方法：表達(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）操作數(shù)之間的相對(duì)次序不變）操作數(shù)之間

19、的相對(duì)次序不變;2）運(yùn)算符的相對(duì)次序不同）運(yùn)算符的相對(duì)次序不同;3）中綴式丟失了括弧信息， 致使運(yùn)算的次序不確定;4)前綴式的運(yùn)算規(guī)則前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式個(gè)最小表達(dá)式; 5)后綴式的運(yùn)算規(guī)則后綴式的運(yùn)算規(guī)則為: 運(yùn)算符在式中出現(xiàn)的順序恰為運(yùn)算符在式中出現(xiàn)的順序恰為 表達(dá)式的運(yùn)算順序表達(dá)式的運(yùn)算順序; 每個(gè)運(yùn)算符和在它之前出現(xiàn)每個(gè)運(yùn)算符和在它之前出現(xiàn) 且且 緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小 表達(dá)式。表達(dá)式。如何從后綴式求值？如何從后綴式求值？先找

20、運(yùn)算符，先找運(yùn)算符， 再找操作數(shù)再找操作數(shù)例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) fl如何從原表達(dá)式求得后綴式？如何從原表達(dá)式求得后綴式？ 每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來(lái)定，在后綴式中，優(yōu)先數(shù)一個(gè)運(yùn)算符來(lái)定，在后綴式中，優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。分析分析 “原表達(dá)式原表達(dá)式” 和和 “后綴式后綴式”中的運(yùn)算符中的運(yùn)算符:原表達(dá)式原表達(dá)式: a + b c d / e f后綴式后綴式: a b c + d e / f 從原表達(dá)式求得后綴式的規(guī)律為：從原表達(dá)式求得

21、后綴式的規(guī)律為：1) 設(shè)立設(shè)立操作數(shù)棧；操作數(shù)棧；2) 設(shè)表達(dá)式的結(jié)束符為設(shè)表達(dá)式的結(jié)束符為“#”， 預(yù)設(shè)預(yù)設(shè)運(yùn)算符棧的運(yùn)算符棧的棧底為棧底為“#”；3) 若若當(dāng)前字符當(dāng)前字符是操作數(shù)是操作數(shù)， 則則直接發(fā)送給后綴式直接發(fā)送給后綴式。4) 若若當(dāng)前當(dāng)前運(yùn)算符的運(yùn)算符的優(yōu)先數(shù)高優(yōu)先數(shù)高于棧頂運(yùn)算于棧頂運(yùn)算符，則符，則進(jìn)棧進(jìn)棧；5) 否則，退出棧頂運(yùn)算符發(fā)送給后綴式否則，退出棧頂運(yùn)算符發(fā)送給后綴式； 6) “(” 對(duì)它之前后的運(yùn)算符對(duì)它之前后的運(yùn)算符起隔離作起隔離作用用，“)”可視為自相應(yīng)左括弧開(kāi)始的可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符。表達(dá)式的結(jié)束符。從原表達(dá)式求得后綴式的規(guī)律為從原表達(dá)式求得

22、后綴式的規(guī)律為：例七、實(shí)現(xiàn)遞歸例七、實(shí)現(xiàn)遞歸 將所有的實(shí)在參數(shù)、返回地址等將所有的實(shí)在參數(shù)、返回地址等信息信息傳傳遞給被調(diào)用函數(shù)遞給被調(diào)用函數(shù)保存保存； 為被調(diào)用函數(shù)的局部變量為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)分配存儲(chǔ)區(qū)； 將將控制轉(zhuǎn)移控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。到被調(diào)用函數(shù)的入口。 當(dāng)在一個(gè)函數(shù)的運(yùn)行期間當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函調(diào)用另一個(gè)函數(shù)數(shù)時(shí)，在時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前運(yùn)行該被調(diào)用函數(shù)之前，需先完成三項(xiàng)任務(wù)：需先完成三項(xiàng)任務(wù)： 保存保存被調(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ù)之前之前，