第七講 棧的應(yīng)用

第三章棧和隊(duì)列棧的應(yīng)用2023/2/51濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2復(fù)習(xí)與回顧棧的特點(diǎn)棧的基本術(shù)語(yǔ)鏈棧順序棧2濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系3

棧的應(yīng)用舉例一、數(shù)制轉(zhuǎn)換二、括號(hào)匹配的檢驗(yàn)三、表達(dá)式求值四、實(shí)現(xiàn)遞歸

本講內(nèi)容3濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系4

算法基于原理：“除基取余法”

即：除以基數(shù)取余數(shù)，逆序排列。

一、數(shù)制轉(zhuǎn)換4濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系5

例如：（1348)10=(2504)8，其運(yùn)算過(guò)程如下：

N

Ndiv8

Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系6voidconversion(){

InitStack(S);

scanf("%d",N);while(N){

Push(S,N%8);N=N/8;}while(!StackEmpty(S))

{

Pop(S,e);printf("%d",e);}}//conversion6濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系7二.括號(hào)匹配的檢驗(yàn)括號(hào)匹配問(wèn)題括號(hào)匹配{[()]}，((){})，()括號(hào)不匹配(()，()]，([)]檢驗(yàn)括號(hào)匹配的方法：“期待的急迫程度”檢查括號(hào)匹配的算法設(shè)一棧遇到左括號(hào)則入棧，遇到右括號(hào)時(shí)，若棧空，則不匹配(右括號(hào)太多)；否則，如果棧頂元素與該右括號(hào)匹配，則出棧；否則不匹配(括號(hào)不配對(duì))。輸入結(jié)束后，若棧為空，則匹配，否則不匹配(左括號(hào)太多)。7濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系81.算術(shù)表達(dá)式的組成操作數(shù)（運(yùn)算對(duì)象或運(yùn)算量）運(yùn)算符界限符（如圓括號(hào)，作用是改變運(yùn)算次序）

其中操作數(shù)可以是常量、變量、函數(shù)、表達(dá)式運(yùn)算符有單目、雙目，我們僅以+、-、*、/四種運(yùn)算為例三.（算術(shù)）表達(dá)式的求值8濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系92.常見(jiàn)表達(dá)式有幾種:

(根據(jù)運(yùn)算符在表達(dá)式中的不同位置)

3*(5–2)中綴表達(dá)式3*(5–2)后綴表達(dá)式前綴表達(dá)式352-**3-529濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系10三種表達(dá)式的特點(diǎn)操作數(shù)之間的相對(duì)次序不變運(yùn)算符的相對(duì)次序可能不同中綴式：必須有括號(hào)信息，否則運(yùn)算順序改變前綴式：無(wú)括號(hào)；連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前出現(xiàn)且緊靠它們的運(yùn)算符構(gòu)成了一個(gè)最小表達(dá)式后綴式：無(wú)括號(hào)；運(yùn)算符的排列順序就是計(jì)算順序，每個(gè)運(yùn)算符加上在它之前且緊靠它的兩個(gè)操作數(shù)構(gòu)成了一個(gè)最小表達(dá)式。10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系113.后綴表達(dá)式的計(jì)算（僅討論個(gè)位數(shù)運(yùn)算）

算法自左至右讀取表達(dá)式中的字符設(shè)一棧存放操作數(shù)當(dāng)讀到運(yùn)算符時(shí)，則取出棧頂?shù)膬蓚€(gè)數(shù)進(jìn)行運(yùn)算，將結(jié)果入棧最終結(jié)果保存在棧中。11濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系12intPostfix(){ InitStack(S); read(c); while(c

!=

'='){

if(isdigit(c)){ read(v);

Push(S,v); }

else

{ Pop(S,b);

Pop(S,a); Push(S,Operate(a,c,b)); } read(c); }

Pop(S,result); returnresult;}12濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系13后綴表達(dá)式求值

用實(shí)型數(shù)棧S存放計(jì)算后綴式的中間及最終結(jié)果，求值算法可描述如下:

棧初始化。從左到右掃描后綴表達(dá)式，重復(fù)下述兩步操作，直到表達(dá)式尾。①?gòu)谋磉_(dá)式中取出下個(gè)TOKEN(操作數(shù)、運(yùn)算符)②CASETOKENOF

操作數(shù)：將操作數(shù)直接入棧S;

運(yùn)算符：出棧兩個(gè)操作數(shù)，對(duì)其進(jìn)行TOKEN操作，結(jié)果壓入棧S

當(dāng)遇到后綴表達(dá)式結(jié)束，棧頂?shù)闹稻褪墙Y(jié)果(應(yīng)是棧中唯一元素)。13濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系14835+562/-*-#

求值883835+83+5=8888562/6/2=38853-885-3=22*88*2=1616-8-16=-8-814濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系154.中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式分析

中綴表達(dá)式1+2*3+(4*5+6)*7后綴表達(dá)式123*+45*6+7*+算法讀到操作數(shù)時(shí)立即輸出運(yùn)算符存放在棧中，遇到運(yùn)算符時(shí)，彈出當(dāng)前棧頂運(yùn)算符直到遇到優(yōu)先級(jí)更低的運(yùn)算符為止。15濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系16中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式

設(shè)中綴表達(dá)式和后綴表達(dá)式分別在數(shù)組IFX和PFX中，用棧S實(shí)現(xiàn)中綴式轉(zhuǎn)為后綴式，對(duì)IFX中表達(dá)式從左到右掃描，設(shè)TOKEN是掃描讀到的符號(hào)，轉(zhuǎn)換算法可描述如下。棧初始化。從左到右掃描數(shù)組IFX，重復(fù)下述兩步操作，直到表達(dá)式尾。

16濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系17

①?gòu)腎PX中取出TOKEN(數(shù)字、運(yùn)算符、左括號(hào)、右括號(hào))；②CASETOKENOF

‘(’：壓入棧S;

操作數(shù)：將操作數(shù)直接送入PFX，后面加一個(gè)空格;

運(yùn)算符：如棧空或TOKEN比棧頂元素優(yōu)先級(jí)高，將TOKEN進(jìn)棧；否則，將棧內(nèi)優(yōu)先級(jí)高于或等于TOKEN的運(yùn)算符，退棧并將退棧元素送入PFX；

‘)’：退棧并將退棧元素送PFX，直到碰到左括號(hào)，左括號(hào)退棧不送PFX。結(jié)束符號(hào):連續(xù)退棧并送退棧元素到PFX，直至?？铡?7濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系18舉例：將中綴表達(dá)式

8-(3+5)*(5-6/2)#

轉(zhuǎn)為后綴表達(dá)式883

835

835+

835+5

835+56

835+562

835+562/-

835+562/-*-

18濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系19表達(dá)式轉(zhuǎn)換的簡(jiǎn)單方法中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式有三步：（1）將中綴表達(dá)式中所有的子表達(dá)式按計(jì)算規(guī)則用嵌套括號(hào)括起來(lái)；（2）順序?qū)⒚繉?duì)括號(hào)中的運(yùn)算符移到相應(yīng)括號(hào)的后面；（3）刪除所有括號(hào)。

例如，將中綴表達(dá)式8-(3+5)*(5-6/2）轉(zhuǎn)為后綴表達(dá)式。按如上步驟：執(zhí)行完上面第一步后為：(8-((3+5)*(5-(6/2))))；執(zhí)行完上面第二步后為：(8((35)+(5(62)/)-)*)-；執(zhí)行完上面第三步后為：835+562/-*-19濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2023/2/5濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系20作業(yè)用棧實(shí)現(xiàn)將中綴表達(dá)式

10+(18+9*3)/15-6#

轉(zhuǎn)換成后綴表達(dá)式并進(jìn)行后綴表達(dá)式的計(jì)算，分別畫出兩個(gè)步驟中的棧的變化示意圖。20濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系四.

棧與遞歸1.函數(shù)調(diào)用與返回的過(guò)程2.遞歸函數(shù)3.遞歸的設(shè)計(jì)原則4.遞歸的優(yōu)點(diǎn)和缺點(diǎn)5.消除遞歸21濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系1.函數(shù)調(diào)用與返回的過(guò)程（1）函數(shù)調(diào)用

當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，

需先完成三項(xiàng)任務(wù)：將返回地址、所有實(shí)參等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。22濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系1.函數(shù)調(diào)用與返回的過(guò)程（2）函數(shù)返回

從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項(xiàng)任務(wù)：保存被調(diào)函數(shù)的計(jì)算結(jié)果；釋放被調(diào)函數(shù)保存局部變量的數(shù)據(jù)區(qū)；依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。函數(shù)嵌套調(diào)用時(shí)，后調(diào)用的函數(shù)先返回。23濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系intmain(){ intn=10; intsn;

sn=sum(n); cout<<sn<<endl;}intsum(intn){ inti,s=0;

for(i=1;i<n;i++) s+=i; returns;}intmain(){ intn=10; intsn;

sn=sum(n); cout<<sn<<endl;}intsum(intn){ inti,s=0;

for(i=1;i<n;i++) s+=i; returns;}main:n=10main:sn=sum:n=10goto:5sum:i=sum:s=0sum:i=11sum:s=55main:sn=55main()sum()24濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2.遞歸函數(shù)函數(shù)直接或間接調(diào)用自身，稱為遞歸(Recursion)。何時(shí)應(yīng)用遞歸？問(wèn)題具有遞歸的數(shù)學(xué)定義使用了遞歸的數(shù)據(jù)結(jié)構(gòu)問(wèn)題存在遞歸的解決方法25濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系遞歸過(guò)程的應(yīng)用（1）（1）問(wèn)題的數(shù)學(xué)定義是遞歸的：求n的階乘n!

longFact(intn){if(n==1)return(1);elsereturn(n*Fact(n-1));}26濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系遞歸過(guò)程的應(yīng)用（1）（1）問(wèn)題的數(shù)學(xué)定義是遞歸的：計(jì)算Fibonacci數(shù)列：0,1,1,2,3,5,8,13,21,…longFib(intn){if(n==1)return0;if(n==2)return1;returnFib(n-1)+Fib(n-2);}27濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系遞歸過(guò)程的應(yīng)用（1）（1）問(wèn)題的數(shù)學(xué)定義是遞歸的：計(jì)算xn（n為整數(shù)，n≥0）28濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系遞歸過(guò)程的應(yīng)用（1）（1）問(wèn)題的數(shù)學(xué)定義是遞歸的：計(jì)算xn（n為整數(shù)，n≥0）doublePower(doublex,intn){if(n==0)return1;if(n==1)returnx;if(n%2==0)returnPower(x*x,n/2);elsereturnx*Power(x*x,n/2);}例如計(jì)算X64只需要6次乘法29濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系voidPrintLinkList(LinkListL){if(L!=NULL){printf(L->data);if(L->next!=NULL){PrintLinkList(L->next);}}}LL->next…以后將要學(xué)習(xí)的廣義表、樹(shù)和二叉樹(shù)等結(jié)構(gòu)也具有遞歸的特點(diǎn)，所以常常使用遞歸算法。遞歸過(guò)程的應(yīng)用（2）（2）數(shù)據(jù)結(jié)構(gòu)是遞歸的：

打印鏈表中各結(jié)點(diǎn)的值30濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系遞歸過(guò)程的應(yīng)用（3）問(wèn)題存在遞歸的解決方法n階Hanoi塔問(wèn)題：假設(shè)有三個(gè)分別命名為X,Y,Z的塔座，在X塔座上插有n個(gè)直徑大小各不相同，依小到大編號(hào)為1，2，…,n的圓盤，要求：把X上的n個(gè)圓盤移到Z上，排列順序相同，移動(dòng)規(guī)則為：每次只能移動(dòng)一個(gè)園盤；園盤可以在任一塔上做多次移動(dòng)；在任何時(shí)刻，大盤不能壓在小盤的上面。XYZ31濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系棧與遞歸的實(shí)現(xiàn):Hanoi數(shù)學(xué)歸納法n=1,OK;設(shè)n=k時(shí)，若可以以Y為輔助塔，把k個(gè)盤從X移動(dòng)到Z;當(dāng)n=k+1時(shí)，方法：把X中k個(gè)盤，以Z為輔助塔，移動(dòng)到Y(jié);把X中第k+1個(gè)盤，移動(dòng)到Z;把Y中k個(gè)盤，以X為輔助塔，移動(dòng)到Z;32濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系問(wèn)題存在遞歸的解決方法

Hanoi(n,a,b,c)表示解決n個(gè)盤子的漢諾塔問(wèn)題（從a搬到c，可以借助b）。解決方法：若n=1，直接將盤子從a搬到c即可；否則，可以分解為如下步驟：Hanoi(n-1,a,c,b)move(n,a,c)Hanoi(n-1,b,a,c)voidHanoi(intn,chara,charb,charc){if(n==1)move(n,a,c);else{Hanoi(n-1,a,c,b);move(n,a,c);

Hanoi(n-1,b,a,c);}}33濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系3.遞歸的設(shè)計(jì)原則如果遞歸設(shè)計(jì)不當(dāng)…容易造成無(wú)窮遞歸，最終會(huì)耗盡應(yīng)用程序的?？臻g，導(dǎo)致棧溢出錯(cuò)誤，使程序失敗。//無(wú)窮遞歸的例子//講不完的故事voidStory(){print(“從前有座山，山上有個(gè)廟，廟里有個(gè)和尚在講故事：”);

Story();}34濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系3.遞歸的設(shè)計(jì)原則（1）基準(zhǔn)情形必須存在不用繼續(xù)遞歸即可解決的情況。（2）不斷推進(jìn)對(duì)于需要遞歸解決的情況，每一次遞歸都要使得求解朝著基準(zhǔn)情況的方向推進(jìn)。（3）遞歸可行性假設(shè)所有的遞歸調(diào)用都能運(yùn)行。（4）合成效益解決一個(gè)問(wèn)題時(shí)，切勿在不同的遞歸調(diào)用中做重復(fù)的工作。35濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系一個(gè)不符合合成效益法則的例子：longFib(intn){if(n==1)return0;if(n==2)return1;returnFib(n-1)+Fib(n-2);}Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)36濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系4.遞歸的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：遞歸函數(shù)結(jié)構(gòu)清晰，程序易讀，正確性容易證明。缺點(diǎn)：反復(fù)的遞歸函數(shù)調(diào)用使得執(zhí)行效率較低。37濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系5.消除遞歸為什么消除遞歸？某些語(yǔ)言不支持函數(shù)的遞歸調(diào)用。在某些關(guān)鍵部分，遞歸算法影響了執(zhí)行的效率。如何消除遞歸？（1）轉(zhuǎn)化為遞推（循環(huán)）。（2）自己管理一個(gè)遞歸工作棧。38濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系（1）遞歸和遞推使用遞推可以有效減少函數(shù)遞歸調(diào)用的次數(shù)，節(jié)省了時(shí)間和空間。//遞推計(jì)算n!longFact(intn){longfactor=1;for(inti=1;i<n;i++)factor=i*factor;