教學(xué)第1章-棧(C++版)課件

第一章棧1ppt課件第一章棧1ppt課件

棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進(jìn)來的壓在底下，隨后一件一件往上堆。取走時(shí)，只能從上面一件一件取。堆和取都在頂部進(jìn)行，底部一般是不動(dòng)的。棧就是一種類似桶堆積物品的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行刪除和插入的一端稱棧頂，另一堆稱棧底。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進(jìn)先出表（LIFO表）。一個(gè)?？梢杂枚ㄩL為Ｎ的數(shù)組Ｓ來表示，用一個(gè)棧指針TOP指向棧頂。若TOP＝0，表示?？?，TOP=N時(shí)棧滿。進(jìn)棧時(shí)TOP加１。退棧時(shí)TOP減１。當(dāng)TOP<0時(shí)為下溢。棧指針在運(yùn)算中永遠(yuǎn)指向棧頂。2ppt課件棧是只能在某一端插入和刪除的特殊線性表。2p1、進(jìn)棧（PUSH）算法①若TOP≥ｎ時(shí)，則給出溢出信息，作出錯(cuò)處理（進(jìn)棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；②TOP++（棧指針加１，指向進(jìn)棧地址）；③S[TOP]=X，結(jié)束（X為新進(jìn)棧的元素）；2、退棧（POP）算法

①若TOP≤0，則給出下溢信息，作出錯(cuò)處理(退棧前先檢查是否已為空棧，空則下溢；不空則作②)；

②X=S[TOP]，（退棧后的元素賦給X）；

③TOP--，結(jié)束（棧指針減１，指向棧頂）。進(jìn)棧、出棧的c++實(shí)現(xiàn)過程程序：#definen100voidpush(ints[],int*top,int*x)//入棧{if(*top==n)printf("overflow");else{(*top)++;s[*top]=*x;}}voidpop(ints[],int*y,int*top)//出棧{if(*top==0)printf("underflow");else{*y=s[*top];(*top)--;}}3ppt課件1、進(jìn)棧（PUSH）算法3ppt課件

對于出棧運(yùn)算中的“下溢”，程序中僅給出了一個(gè)標(biāo)志信息，而在實(shí)際應(yīng)用中，下溢可用來作為控制程序轉(zhuǎn)移的判斷標(biāo)志，是十分有用的。對于入棧運(yùn)算中的“上溢”，則是一種致命的錯(cuò)誤，將使程序無法繼續(xù)運(yùn)行，所以要設(shè)法避免。堆棧的數(shù)組模擬十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是實(shí)現(xiàn)計(jì)算的基本問題，解決方法很多，下面給出一種算法原理：N=(N/d)×d＋N%d（其中/為整除運(yùn)算，%為求余運(yùn)算）。例如：(1348)10＝(2504)8運(yùn)算過程如下：4ppt課件對于出棧運(yùn)算中的“下溢”，程序中僅給出了一個(gè)標(biāo)1、填空：(9413)10=()8=()16=()22、數(shù)制轉(zhuǎn)化程序#include<cstdlib>#include<iostream>usingnamespacestd;#definesize100inta[size+1],n,d,i=0,j;main(){cout<<"Pleaseenteranumber(N)base10:";cin>>n;cout<<"pleaseenteranumber(d):";cin>>d;do{a[++i]=n%d;n=n/d;}while(n!=0);for(j=i;j>=1;j--)cout<<a[j];return0;}3、火車站列車調(diào)度示意圖如下，假設(shè)調(diào)度站兩側(cè)的軌道為單向行駛軌道。

①如果進(jìn)站的車廂序列為123，則可能的出站車廂序列是什么？

②如果進(jìn)站的車廂序列為123456，問能否得到135426和435612的出站序列。5ppt課件1、填空：5ppt課件【例1】括號的匹配（表達(dá)式的合法性檢查）【問題描述】假設(shè)一個(gè)表達(dá)式有英文字母（小寫）、運(yùn)算符（+，—，*，/）和左右小（圓）括號構(gòu)成，以“@”作為表達(dá)式的結(jié)束符。請編寫一個(gè)程序檢查表達(dá)式中的左右圓括號是否匹配，若匹配，則返回“YES”；否則返回“NO”。假設(shè)表達(dá)式長度小于255，左圓括號少于20個(gè)?！舅惴ǚ治觥考僭O(shè)輸入的字符串存儲在c中（charc[256]

）。我們可以定義一個(gè)棧：chars[maxn+1];inttop;

用它來存放表達(dá)式中從左往右的左圓括號（maxn=20）。算法的思路為：順序（從左往右）掃描表達(dá)式的每個(gè)字符c[i]，若是“（”，則讓它進(jìn)棧；若遇到的是“）”，則讓棧頂元素出棧；當(dāng)棧發(fā)生下溢或當(dāng)表達(dá)式處理完畢而棧非空時(shí)，都表示不匹配，返回“NO”；否則表示匹配，返回“YES”。

#include<cstdio>#include<cstdlib>usingnamespacestd;#definemaxn20charc[256];booljudge(charc[256])6ppt課件【例1】括號的匹配（表達(dá)式的合法性檢查）#include<{inttop=0,i=0;while(c[i]!='@'){if(c[i]=='(')top++;if(c[i]==')'){if(top>0)top--;elsereturn0;}i++;}if(top!=0)return0;//檢測棧是否為空。不空則說明有未匹配的括號

elsereturn1;}main(){scanf("%s",c);if(judge(c))printf("YES");elseprintf("NO");return0;}7ppt課件{7ppt課件【例2】編程求一個(gè)后綴表達(dá)式的值【問題描述】從鍵盤讀入一個(gè)后綴表達(dá)式（字符串），只含有0-9組成的運(yùn)算數(shù)及加（+）、減（—）、乘（*）、除（/）四種運(yùn)算符。每個(gè)運(yùn)算數(shù)之間用一個(gè)空格隔開，不需要判斷給你的表達(dá)式是否合法。以@作為結(jié)束標(biāo)志?！舅惴ǚ治觥亢缶Y表達(dá)式的處理過程很簡單，過程如下：掃描后綴表達(dá)式，凡遇操作數(shù)則將之壓進(jìn)堆棧，遇運(yùn)算符則從堆棧中彈出兩個(gè)操作數(shù)進(jìn)行該運(yùn)算，將運(yùn)算結(jié)果壓棧，然后繼續(xù)掃描，直到后綴表達(dá)式被掃描完畢為止，此時(shí)棧底元素即為該后綴表達(dá)式的值。比如，16–9*(4+3)轉(zhuǎn)換成后綴表達(dá)式為：

16□9□4□3□+*–，在字符數(shù)組A中的形式為：棧中的變化情況：運(yùn)行結(jié)果：-478ppt課件【例2】編程求一個(gè)后綴表達(dá)式的值棧中的變化情況：運(yùn)行結(jié)果：-#include<cstdio>#include<cstdlib>#include<string>#include<cstring>usingnamespacestd;intstack[101];chars[256];intcomp(chars[256]){inti=0,top=0,x,y;while(i<=strlen(s)-2){switch(s[i]){case'+':stack[--top]+=stack[top+1];break;case'-':stack[--top]-=stack[top+1];break;case'*':stack[--top]*=stack[top+1];break;case'/':stack[--top]/=stack[top+1];break;default:x=0;while(s[i]!='')x=x*10+s[i++]-'0';stack[++top]=x;break;}i++;}//whilereturnstack[top];}9ppt課件#include<cstdio>9ppt課件main(){printf("inputastring(@_over):");gets(s);printf("result=%d",comp(s));return0;}10ppt課件main()10ppt課件【例3】車廂調(diào)度【問題描述】有一個(gè)火車站，鐵路如圖所示，每輛火車從A駛?cè)?，再從B方向駛出，同時(shí)它的車廂可以重新組合。假設(shè)從A方向駛來的火車有n節(jié)（n<=1000），分別按照順序編號為1，2，3，…，n。假定在進(jìn)入車站前，每節(jié)車廂之間都不是連著的，并且它們可以自行移動(dòng)到B處的鐵軌上。另外假定車站C可以停放任意多節(jié)車廂。但是一旦進(jìn)入車站C，它就不能再回到A方向的鐵軌上了，并且一旦當(dāng)它進(jìn)入B方向的鐵軌，它就不能再回到車站C。

負(fù)責(zé)車廂調(diào)度的工作人員需要知道能否使它以a1,a2,…,an的順序從B方向駛出，請來判斷能否得到指定的車廂順序?！据斎搿?/p>

輸入文件的第一行為一個(gè)整數(shù)n，其中n<=1000，表示有n節(jié)車廂，第二行為n個(gè)數(shù)字，表示指定的車廂順序?！据敵觥?/p>

如果可以得到指定的車廂順序，則輸出一個(gè)字符串”YES”，否則輸出”NO”（注意要大寫，不包含引號）?！据斎霕永?/p>

5

54321【輸出樣例】

YES11ppt課件【例3】車廂調(diào)度11ppt課件分析：

該題就是前面思考題的一部分。車站C相當(dāng)于一個(gè)棧。我們用模擬法來做，假設(shè)我們已經(jīng)處理了前i-1節(jié)從B方向駛出的車廂，我們現(xiàn)在要讓ai駛出。若ai不在車站C中，我們就讓若干車廂從A方向駛?cè)胲囌綜，直到ai駛?cè)?，再將它從B方向駛出；若ai在車站C中，如果它是車站C中停在最前面的，則將它從B方向駛出，否則原問題無解。如樣例中，出棧序列是35421，模擬過程如下：

①一開始棧為空

②由于3不在棧中，就需要把1,2,3依次進(jìn)棧，再出棧，這樣符合出棧序列第一個(gè)數(shù)是3，當(dāng)前棧為{1,2}③第2個(gè)出棧的是5,5不在棧中，則就把4,5壓棧，再出棧就可以得到5，此時(shí)棧為{1,2，4}④第3個(gè)出棧的是4，正好是棧頂元素，直接出棧，棧變?yōu)閧1,2}⑤第4個(gè)出棧的是2，正好是棧頂元素，直接出棧，棧變?yōu)閧2}⑥第5個(gè)出棧的是1，正好是棧頂元素，直接出棧，棧變?yōu)閧}在模擬過程中沒有碰到要出棧的數(shù)在棧中但不是棧頂元素的情況，所以該方案可行。12ppt課件分析：12ppt課件【參考程序】#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=1010;intstack[N],a[N];inttop,n;intmain(){ cin>>n; for(inti=1;i<=n;++i) cin>>a[i]; top=0; for(inti=1,cur=1;i<=n;++i)//cur為當(dāng)前要從A方向駛?cè)氲能噹?/p>

{ while(cur<=a[i]) stack[++top]=cur++;

if(stack[top]==a[i]) --top; else { cout<<"NO"<<endl; return0; } } cout<<"YES"<<endl; return0;}13ppt課件【參考程序】13ppt課件1、表達(dá)式括號匹配(stack.cpp)【問題描述】假設(shè)一個(gè)表達(dá)式有英文字母（小寫）、運(yùn)算符（+，—，*，/）和左右?。▓A）括號構(gòu)成，以“@”作為表達(dá)式的結(jié)束符。請編寫一個(gè)程序檢查表達(dá)式中的左右圓括號是否匹配，若匹配，則返回“YES”；否則返回“NO”。表達(dá)式長度小于255，左圓括號少于20個(gè)?！据斎胛募枯斎胛募tack.in包括一行數(shù)據(jù)，即表達(dá)式，【輸出文件】輸出文件stack.out包括一行，即“YES”或“NO”?！緲永斎?】2*(x+y)/(1-x)@【樣例輸出1】YES【樣例輸入2】(25+x)*(a*(a+b+b)@【樣例輸出2】NO【上機(jī)練習(xí)】14ppt課件1、表達(dá)式括號匹配(stack.cpp)【上機(jī)練習(xí)】14pp2、括弧匹配檢驗(yàn)(check.cpp)【問題描述】假設(shè)表達(dá)式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，如（［］（））或［（［］［］）］等為正確的匹配，［（]）或（［］（）或(())）均為錯(cuò)誤的匹配。現(xiàn)在的問題是，要求檢驗(yàn)一個(gè)給定表達(dá)式中的括弧是否正確匹配？輸入一個(gè)只包含圓括號和方括號的字符串，判斷字符串中的括號是否匹配，匹配就輸出“OK”，不匹配就輸出“Wrong”。輸入一個(gè)字符串：［（［］［］）］，輸出：OK【輸入格式】輸入僅一行字符（字符個(gè)數(shù)小于255）【輸出格式】匹配就輸出“OK”，不匹配就輸出“Wrong”?！据斎霕永縞heck.in［（］）【輸出樣例】check.outWrong15ppt課件2、括弧匹配檢驗(yàn)(check.cpp)15ppt課件3、字符串匹配問題【問題描述】字符串中只含有括號(),[],<>,{},判斷輸入的字符串中括號是否匹配。如果括號有互相包含的形式，從內(nèi)到外必須是<>,(),[],{}，例如。輸入:[()]輸出:YES，而輸入([])，([])都應(yīng)該輸出NO?！据斎敫袷健縮trs.in

文件的第一行為一個(gè)整數(shù)n，表示以下有多少個(gè)由括好組成的字符串。接下來的n行，每行都是一個(gè)由括號組成的長度不超過255的字符串?！据敵龈袷健縮trs.out

在輸出文件中有N行，每行都是YES或NO?！据斎霕永?{}{}<><>()()[][]{{}}{{}}<<>><<>>(())(())[[]][[]]{{}}{{}}<<>><<>>(())(())[[]][[]]{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]【輸出標(biāo)例】YESYESYESYESNO16ppt課件3、字符串匹配問題16ppt課件4、計(jì)算(calc.cpp)【問題描述】小明在你的幫助下，破密了Ferrari設(shè)的密碼門，正要往前走，突然又出現(xiàn)了一個(gè)密碼門，門上有一個(gè)算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”求出的值就是密碼。小明數(shù)學(xué)學(xué)得不好，還需你幫他的忙。(“/”用整數(shù)除法)【輸入】輸入文件calc.in共1行，為一個(gè)算式?！据敵觥枯敵鑫募alc.out共1行，就是密碼?！据斎霕永縞alc.in1+(3+2)*(7^2+6*9)/(2)【輸出樣例】calc.out258【限制】100%的數(shù)據(jù)滿足：算式長度<=30其中所有數(shù)據(jù)在231-1的范圍內(nèi)。17ppt課件4、計(jì)算(calc.cpp)17ppt課件5、車廂調(diào)度(train.cpp)【問題描述】有一個(gè)火車站，鐵路如圖所示，每輛火車從A駛?cè)?，再從B方向駛出，同時(shí)它的車廂可以重新組合。假設(shè)從A方向駛來的火車有n節(jié)（n<=1000），分別按照順序編號為1，2，3，…，n。假定在進(jìn)入車站前，每節(jié)車廂之間都不是連著的，并且它們可以自行移動(dòng)到B處的鐵軌上。另外假定車站C可以停放任意多節(jié)車廂。但是一旦進(jìn)入車站C，它就不能再回到A方向的鐵軌上了，并且一旦當(dāng)它進(jìn)入B方向的鐵軌，它就不能再回到車站C。負(fù)責(zé)車廂調(diào)度的工作人員需要知道能否使它以a1,a2,…,an的順序從B方向駛出，請來判斷能否得到指定的車廂順序?！据斎搿縯rain.in

輸入文件的第一行為一個(gè)整數(shù)n，其中n<=1000，表示有n節(jié)車廂，第二行為n個(gè)數(shù)字，表示指定的車廂順序?！据敵觥縯rain.out

如果可以得到指定的車廂順序，則輸出一個(gè)字符串”YES”，否則輸出”NO”（注意要大寫，不包含引號）。【輸入樣例】554321【輸出樣例】YES18ppt課件5、車廂調(diào)度(train.cpp)18ppt課件6、中綴表達(dá)式值(Expr.cpp)【問題描述】輸入一個(gè)中綴表達(dá)式（由0-9組成的運(yùn)算數(shù)、加+減—乘*除/四種運(yùn)算符、左右小括號組成。注意“—”也可作為負(fù)數(shù)的標(biāo)志，表達(dá)式以“@”作為結(jié)束符），判斷表達(dá)式是否合法，如果不合法，請輸出“NO”；否則請把表達(dá)式轉(zhuǎn)換成后綴形式，再求出后綴表達(dá)式的值并輸出。注意：必須用棧操作，不能直接輸出表達(dá)式的值。如果再考慮是實(shí)數(shù)運(yùn)算呢？【輸入文件】Expr.in

輸入文件的第一行為一個(gè)以@結(jié)束的字符串?！据敵鑫募縀xpr.out

如果表達(dá)式不合法，請輸出“NO”，要求大寫。如果表達(dá)式合法，請輸出計(jì)算結(jié)果。【輸入樣例】1＋2×8―9【輸出樣例】819ppt課件6、中綴表達(dá)式值(Expr.cpp)19ppt課件第一章棧20ppt課件第一章棧1ppt課件

棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進(jìn)來的壓在底下，隨后一件一件往上堆。取走時(shí)，只能從上面一件一件取。堆和取都在頂部進(jìn)行，底部一般是不動(dòng)的。棧就是一種類似桶堆積物品的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行刪除和插入的一端稱棧頂，另一堆稱棧底。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進(jìn)先出表（LIFO表）。一個(gè)?？梢杂枚ㄩL為Ｎ的數(shù)組Ｓ來表示，用一個(gè)棧指針TOP指向棧頂。若TOP＝0，表示?？?，TOP=N時(shí)棧滿。進(jìn)棧時(shí)TOP加１。退棧時(shí)TOP減１。當(dāng)TOP<0時(shí)為下溢。棧指針在運(yùn)算中永遠(yuǎn)指向棧頂。21ppt課件棧是只能在某一端插入和刪除的特殊線性表。2p1、進(jìn)棧（PUSH）算法①若TOP≥ｎ時(shí)，則給出溢出信息，作出錯(cuò)處理（進(jìn)棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；②TOP++（棧指針加１，指向進(jìn)棧地址）；③S[TOP]=X，結(jié)束（X為新進(jìn)棧的元素）；2、退棧（POP）算法

①若TOP≤0，則給出下溢信息，作出錯(cuò)處理(退棧前先檢查是否已為空棧，空則下溢；不空則作②)；

②X=S[TOP]，（退棧后的元素賦給X）；

③TOP--，結(jié)束（棧指針減１，指向棧頂）。進(jìn)棧、出棧的c++實(shí)現(xiàn)過程程序：#definen100voidpush(ints[],int*top,int*x)//入棧{if(*top==n)printf("overflow");else{(*top)++;s[*top]=*x;}}voidpop(ints[],int*y,int*top)//出棧{if(*top==0)printf("underflow");else{*y=s[*top];(*top)--;}}22ppt課件1、進(jìn)棧（PUSH）算法3ppt課件

對于出棧運(yùn)算中的“下溢”，程序中僅給出了一個(gè)標(biāo)志信息，而在實(shí)際應(yīng)用中，下溢可用來作為控制程序轉(zhuǎn)移的判斷標(biāo)志，是十分有用的。對于入棧運(yùn)算中的“上溢”，則是一種致命的錯(cuò)誤，將使程序無法繼續(xù)運(yùn)行，所以要設(shè)法避免。堆棧的數(shù)組模擬十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是實(shí)現(xiàn)計(jì)算的基本問題，解決方法很多，下面給出一種算法原理：N=(N/d)×d＋N%d（其中/為整除運(yùn)算，%為求余運(yùn)算）。例如：(1348)10＝(2504)8運(yùn)算過程如下：23ppt課件對于出棧運(yùn)算中的“下溢”，程序中僅給出了一個(gè)標(biāo)1、填空：(9413)10=()8=()16=()22、數(shù)制轉(zhuǎn)化程序#include<cstdlib>#include<iostream>usingnamespacestd;#definesize100inta[size+1],n,d,i=0,j;main(){cout<<"Pleaseenteranumber(N)base10:";cin>>n;cout<<"pleaseenteranumber(d):";cin>>d;do{a[++i]=n%d;n=n/d;}while(n!=0);for(j=i;j>=1;j--)cout<<a[j];return0;}3、火車站列車調(diào)度示意圖如下，假設(shè)調(diào)度站兩側(cè)的軌道為單向行駛軌道。

①如果進(jìn)站的車廂序列為123，則可能的出站車廂序列是什么？

②如果進(jìn)站的車廂序列為123456，問能否得到135426和435612的出站序列。24ppt課件1、填空：5ppt課件【例1】括號的匹配（表達(dá)式的合法性檢查）【問題描述】假設(shè)一個(gè)表達(dá)式有英文字母（小寫）、運(yùn)算符（+，—，*，/）和左右?。▓A）括號構(gòu)成，以“@”作為表達(dá)式的結(jié)束符。請編寫一個(gè)程序檢查表達(dá)式中的左右圓括號是否匹配，若匹配，則返回“YES”；否則返回“NO”。假設(shè)表達(dá)式長度小于255，左圓括號少于20個(gè)?！舅惴ǚ治觥考僭O(shè)輸入的字符串存儲在c中（charc[256]

）。我們可以定義一個(gè)棧：chars[maxn+1];inttop;

用它來存放表達(dá)式中從左往右的左圓括號（maxn=20）。算法的思路為：順序（從左往右）掃描表達(dá)式的每個(gè)字符c[i]，若是“（”，則讓它進(jìn)棧；若遇到的是“）”，則讓棧頂元素出棧；當(dāng)棧發(fā)生下溢或當(dāng)表達(dá)式處理完畢而棧非空時(shí)，都表示不匹配，返回“NO”；否則表示匹配，返回“YES”。

#include<cstdio>#include<cstdlib>usingnamespacestd;#definemaxn20charc[256];booljudge(charc[256])25ppt課件【例1】括號的匹配（表達(dá)式的合法性檢查）#include<{inttop=0,i=0;while(c[i]!='@'){if(c[i]=='(')top++;if(c[i]==')'){if(top>0)top--;elsereturn0;}i++;}if(top!=0)return0;//檢測棧是否為空。不空則說明有未匹配的括號

elsereturn1;}main(){scanf("%s",c);if(judge(c))printf("YES");elseprintf("NO");return0;}26ppt課件{7ppt課件【例2】編程求一個(gè)后綴表達(dá)式的值【問題描述】從鍵盤讀入一個(gè)后綴表達(dá)式（字符串），只含有0-9組成的運(yùn)算數(shù)及加（+）、減（—）、乘（*）、除（/）四種運(yùn)算符。每個(gè)運(yùn)算數(shù)之間用一個(gè)空格隔開，不需要判斷給你的表達(dá)式是否合法。以@作為結(jié)束標(biāo)志?！舅惴ǚ治觥亢缶Y表達(dá)式的處理過程很簡單，過程如下：掃描后綴表達(dá)式，凡遇操作數(shù)則將之壓進(jìn)堆棧，遇運(yùn)算符則從堆棧中彈出兩個(gè)操作數(shù)進(jìn)行該運(yùn)算，將運(yùn)算結(jié)果壓棧，然后繼續(xù)掃描，直到后綴表達(dá)式被掃描完畢為止，此時(shí)棧底元素即為該后綴表達(dá)式的值。比如，16–9*(4+3)轉(zhuǎn)換成后綴表達(dá)式為：

16□9□4□3□+*–，在字符數(shù)組A中的形式為：棧中的變化情況：運(yùn)行結(jié)果：-4727ppt課件【例2】編程求一個(gè)后綴表達(dá)式的值棧中的變化情況：運(yùn)行結(jié)果：-#include<cstdio>#include<cstdlib>#include<string>#include<cstring>usingnamespacestd;intstack[101];chars[256];intcomp(chars[256]){inti=0,top=0,x,y;while(i<=strlen(s)-2){switch(s[i]){case'+':stack[--top]+=stack[top+1];break;case'-':stack[--top]-=stack[top+1];break;case'*':stack[--top]*=stack[top+1];break;case'/':stack[--top]/=stack[top+1];break;default:x=0;while(s[i]!='')x=x*10+s[i++]-'0';stack[++top]=x;break;}i++;}//whilereturnstack[top];}28ppt課件#include<cstdio>9ppt課件main(){printf("inputastring(@_over):");gets(s);printf("result=%d",comp(s));return0;}29ppt課件main()10ppt課件【例3】車廂調(diào)度【問題描述】有一個(gè)火車站，鐵路如圖所示，每輛火車從A駛?cè)?，再從B方向駛出，同時(shí)它的車廂可以重新組合。假設(shè)從A方向駛來的火車有n節(jié)（n<=1000），分別按照順序編號為1，2，3，…，n。假定在進(jìn)入車站前，每節(jié)車廂之間都不是連著的，并且它們可以自行移動(dòng)到B處的鐵軌上。另外假定車站C可以停放任意多節(jié)車廂。但是一旦進(jìn)入車站C，它就不能再回到A方向的鐵軌上了，并且一旦當(dāng)它進(jìn)入B方向的鐵軌，它就不能再回到車站C。

負(fù)責(zé)車廂調(diào)度的工作人員需要知道能否使它以a1,a2,…,an的順序從B方向駛出，請來判斷能否得到指定的車廂順序?！据斎搿?/p>

輸入文件的第一行為一個(gè)整數(shù)n，其中n<=1000，表示有n節(jié)車廂，第二行為n個(gè)數(shù)字，表示指定的車廂順序?！据敵觥?/p>

如果可以得到指定的車廂順序，則輸出一個(gè)字符串”YES”，否則輸出”NO”（注意要大寫，不包含引號）?！据斎霕永?/p>

5

54321【輸出樣例】

YES30ppt課件【例3】車廂調(diào)度11ppt課件分析：

該題就是前面思考題的一部分。車站C相當(dāng)于一個(gè)棧。我們用模擬法來做，假設(shè)我們已經(jīng)處理了前i-1節(jié)從B方向駛出的車廂，我們現(xiàn)在要讓ai駛出。若ai不在車站C中，我們就讓若干車廂從A方向駛?cè)胲囌綜，直到ai駛?cè)?，再將它從B方向駛出；若ai在車站C中，如果它是車站C中停在最前面的，則將它從B方向駛出，否則原問題無解。如樣例中，出棧序列是35421，模擬過程如下：

①一開始棧為空

②由于3不在棧中，就需要把1,2,3依次進(jìn)棧，再出棧，這樣符合出棧序列第一個(gè)數(shù)是3，當(dāng)前棧為{1,2}③第2個(gè)出棧的是5,5不在棧中，則就把4,5壓棧，再出棧就可以得到5，此時(shí)棧為{1,2，4}④第3個(gè)出棧的是4，正好是棧頂元素，直接出棧，棧變?yōu)閧1,2}⑤第4個(gè)出棧的是2，正好是棧頂元素，直接出棧，棧變?yōu)閧2}⑥第5個(gè)出棧的是1，正好是棧頂元素，直接出棧，棧變?yōu)閧}在模擬過程中沒有碰到要出棧的數(shù)在棧中但不是棧頂元素的情況，所以該方案可行。31ppt課件分析：12ppt課件【參考程序】#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=1010;intstack[N],a[N];inttop,n;intmain(){ cin>>n; for(inti=1;i<=n;++i) cin>>a[i]; top=0; for(inti=1,cur=1;i<=n;++i)//cur為當(dāng)前要從A方向駛?cè)氲能噹?/p>

{ while(cur<=a[i]) stack[++top]=cur++;

if(stack[top]==a[i]) --top; else { cout<<"NO"<<endl; return0; } } cout<<"YES"<<endl; return0;}32ppt課件【參考程序】13ppt課件1、表達(dá)式括號匹配(stack.cpp)【問題描述】假設(shè)一個(gè)表達(dá)式有英文字母（小寫）、運(yùn)算符（+，—，*，/）和左右?。▓A）括號構(gòu)成，以“@”作為表達(dá)式的結(jié)束符。請編寫一個(gè)程序檢查表達(dá)式中的左右圓括號是否匹配，若匹配，則返回“YES”；否則返回“NO”。表達(dá)式長度小于255，左圓括號少于20個(gè)。【輸入文件】輸入文件stack.in包括一行數(shù)據(jù)，即表達(dá)式，【輸出文件】輸出文件stack.out包括一行，即“YES”或“NO”?！緲永斎?】2*(x+y)/(1-x)@【樣例輸出1】YES【樣例輸入2】(25+x)*(a*(a+b+b)@【樣例輸出2】NO【上機(jī)練習(xí)】33ppt課件1、表達(dá)式括號匹配(stack.cpp)【上機(jī)練習(xí)】14pp2、括弧匹配檢驗(yàn)(check.cpp)【問題描述】假設(shè)表達(dá)式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，如（［］（））或［（［］［］）］等為正確的匹配，［（]）或（［］（）或(())）均為錯(cuò)誤的匹配?，F(xiàn)在的問題是，要求檢驗(yàn)一個(gè)給定表達(dá)式中的括弧是否正確匹配？輸入一個(gè)只包含圓括號和方括號的字符串，判斷字符串中的括號是否匹配，匹配就輸出“OK”，不匹配就輸出“Wrong”。輸入一個(gè)字符串：［（［］［］）］，輸出：OK【輸入格式】輸入僅一行字符（字符個(gè)數(shù)小于255）【輸出格式】匹配就輸出“OK”，不匹配就輸出“Wrong”。【輸入樣例】check.in［（］）【輸出樣例】check.outWrong34ppt課件2、括弧匹配檢驗(yàn)(check.cpp)15ppt課件3、字符串匹配問題【問題描述】字符串中只含有括號(),[],<>,{},判斷輸入的字符串中括號是否匹配。如果括號有互相包含的形式，從內(nèi)到外必須是<>,(),[],{}，例如。輸入:[()]輸出:YES，而輸入([])，([])都應(yīng)該輸出NO。【輸入格式】strs.in

文件的第一行為一個(gè)整數(shù)n，表示以下有多少個(gè)由括好組成