《數(shù)據(jù)結(jié)構(gòu)：思想與方法》第三章棧

1第三章棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用2棧后進(jìn)先出(LIFO,LastInFirstOut)或先進(jìn)后出(FILO,FirstInLastOut)結(jié)構(gòu)，最先(晚)到達(dá)棧的結(jié)點(diǎn)將最晚(先)被刪除。

乒乓球進(jìn)盒、出盒3相關(guān)概念an-1an-2…a1a0…出棧進(jìn)棧棧底棧頂4相關(guān)概念棧底(bottom)：結(jié)構(gòu)的首部(結(jié)點(diǎn)最早到達(dá)的部分)棧頂（top）：結(jié)構(gòu)的尾部(結(jié)點(diǎn)最晚到達(dá)的部分)出棧（Pop）：結(jié)點(diǎn)從棧頂刪除進(jìn)棧（Push）：結(jié)點(diǎn)在棧頂位置插入空棧：棧中結(jié)點(diǎn)個數(shù)為零時5棧的運(yùn)算創(chuàng)建一個棧create()：創(chuàng)建一個空的棧；進(jìn)棧push(x)：將x插入棧中，使之成為棧頂元素；出棧pop()：刪除棧頂元素并返回棧頂元素值；讀棧頂元素top()：返回棧頂元素值但不刪除棧頂元素；判?？読sEmpty()：若棧為空，返回true，否則返回false。6棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用7棧的順序?qū)崿F(xiàn)用連續(xù)的空間存儲棧中的結(jié)點(diǎn)，即數(shù)組進(jìn)棧和出?？偸窃跅ｍ斠欢诉M(jìn)行，不會引起類似順序表中的大量數(shù)據(jù)的移動。用數(shù)組的后端表示棧頂。an…a1a0top_p棧底maxSizeelem8順序存儲時的運(yùn)算實(shí)現(xiàn)create()：按照用戶估計的棧的規(guī)模申請一個動態(tài)數(shù)組，將數(shù)組地址保存在data中，數(shù)組規(guī)模保存在maxSize中，并設(shè)top_p的值為-1。push(x)：將top_p加1，將x放入top_p指出的位置中。但要注意數(shù)組滿的情況。pop()：返回top_p指出的位置中的值并將top_p減1。top()：與pop類似，只是不需要將top_p減1。isEmpty()：若top_p的值為-1，返回true，否則返回false。9順序?qū)崿F(xiàn)性能分析除了進(jìn)棧操作以外，所有運(yùn)算實(shí)現(xiàn)的時間復(fù)雜度都是O（1）。進(jìn)棧運(yùn)算在最壞情況下的時間復(fù)雜度是O（N）。但最壞情況在N次進(jìn)棧操作中至多出現(xiàn)一次。如果把擴(kuò)展數(shù)組規(guī)模所需的時間均攤到每個插入操作，每個插入只多了一個拷貝操作，因此從平均的意義上講，插入運(yùn)算還是常量的時間復(fù)雜度。這種分析方法稱為均攤分析法。10棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用11棧的鏈接實(shí)現(xiàn)棧的操作都是在棧頂進(jìn)行的，不需要找某一元素的直接前驅(qū)的操作，因此不需要雙鏈表，用單鏈表就足夠了，而且不需要頭結(jié)點(diǎn)對棧來講，只需要考慮棧頂元素的插入刪除。從棧的基本運(yùn)算的實(shí)現(xiàn)方便性考慮，可將單鏈表的頭指針指向棧頂。12棧的鏈接實(shí)現(xiàn)an-1an-2a0…∧top_p13鏈接存儲時的運(yùn)算實(shí)現(xiàn)create()：將top_p設(shè)為空指針。push(x)：將x插入到單鏈表的表頭voidpush(x){p=new結(jié)點(diǎn)；

p指向的結(jié)點(diǎn)的數(shù)據(jù)部分=x；

p指向的結(jié)點(diǎn)的指針部分=top_p；

top_p=p;}14鏈接存儲時的運(yùn)算實(shí)現(xiàn)pop()：刪除表頭元素dataTypepop(){p=top_p;top_p=top_p指向的結(jié)點(diǎn)的指針部分；

x=p指向的結(jié)點(diǎn)的數(shù)據(jù)部分；

deletep;returnx;}15鏈接存儲時的運(yùn)算實(shí)現(xiàn)top()：返回top_p指向的結(jié)點(diǎn)的值。isEmpty()：若top_p的值為空指針，返回true，否則返回false。16鏈接棧的性能分析由于所有的操作都是對棧頂?shù)牟僮?，郵展中的元素個數(shù)無關(guān)。所以，所有運(yùn)算的時間復(fù)雜度都是O（1）17棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用18棧的抽象類template<classelemType>classstack{public: virtualboolisEmpty()const=0; virtualvoidpush(constelemType&x)=0; virtualelemTypepop()=0;virtualelemTypetop()const=0; virtual~stack(){}};19順序棧類template<classelemType>classseqStack:publicstack<elemType>{private:elemType*elem; inttop_p; intmaxSize; voiddoubleSpace();20public:seqStack(intinitSize=10){ elem=newelemType[initSize]; maxSize=initSize;top_p=-1;}

~seqStack(){delete[]elem;}boolisEmpty()const{returntop_p==-1;}21voidpush(constelemType&x){ if(top_p==maxSize-1)doubleSpace(); elem[++top_p]=x;}

elemTypepop(){returnelem[top_p--];}

elemTypetop()const{returnelem[top_p];} };22doubleSpacetemplate<classelemType>voidseqStack<elemType>::doubleSpace(){

elemType*tmp=elem;

elem=newelemType[2*maxSize]; for(inti=0;i<maxSize;++i) elem[i]=tmp[i];

maxSize*=2; delete[]tmp;}23鏈接棧類template<classelemType>classlinkStack:publicstack<elemType>

{private:structnode{elemTypedata;

node*next; node(constelemType&x,node*N=NULL) {data=x;next=N;} node():next(NULL){} ~node(){} };node*elem;24public:linkStack(){elem=NULL;}

~linkStack();boolisEmpty()const{returnelem==NULL;}voidpush(constelemType&x){node*tmp=newnode(x,elem);

elem=tmp;}elemTypepop(){node*tmp=elem;elemTypex=tmp->data; elem=elem->next; deletetmp;

returnx;}elemTypetop()const{returnelem->data; } };25析構(gòu)函數(shù)template<classelemType>linkStack<elemType>::~linkStack(){ node*tmp; while(elem!=NULL){ tmp=elem; elem=elem->next; deletetmp; }}26棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用27STL中的棧棧本質(zhì)上是一個線性表，在STL中棧類是借助于線性表類實(shí)現(xiàn)的。STL中的棧提供四個標(biāo)準(zhǔn)運(yùn)算：push、pop、top和empty。在STL中，借助于其他容器存儲數(shù)據(jù)的容器稱為容器適配器。棧就是一個容器適配器28棧的類模板定義一個棧對象要指明棧中元素的類型以及借助于哪一個容器，因此棧的類模板有兩個模板參數(shù)：棧元素類型和所借助的容器類型。?？梢越柚娜萜饔衯ector,list和deque。棧的類模板的第二個參數(shù)帶有缺省值deque29STL棧的使用#include<iostream>#include<stack>usingnamespacestd;intmain(){stack<int,vector<int>>s1;stack<int,list<int>>s2;inti;for(i=0;i<10;++i)s1.push(i);while(!s1.empty()){cout<<s1.top()<<'';s1.pop();}cout<<endl;for(i=0;i<10;++i)s2.push(i);while(!s2.empty()){cout<<s2.top()<<'';s2.pop();}cout<<endl;return0;}輸出：987654321030棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用31棧的應(yīng)用遞歸函數(shù)的非遞歸實(shí)現(xiàn)符號平衡檢查表達(dá)式的計算32棧的應(yīng)用—遞歸函數(shù)的非遞歸實(shí)現(xiàn)遞歸的本質(zhì)是函數(shù)調(diào)用，而函數(shù)調(diào)用是通過棧實(shí)現(xiàn)的。因此，遞歸可以用棧消除。voidf1(){…r1:f2();r2:…}voidf2(){…t1:f3();t2:…}voidf3(){……}33函數(shù)執(zhí)行過程f1f2f3r1t1r2t234函數(shù)調(diào)用的實(shí)現(xiàn)設(shè)置一個棧模擬函數(shù)調(diào)用。當(dāng)發(fā)生函數(shù)調(diào)用時，將當(dāng)前的函數(shù)的現(xiàn)場進(jìn)棧。調(diào)用f2前Top調(diào)用f2后Topr2調(diào)用f3后Topr2t2返回f2后Topr2返回f1后Top35遞歸遞歸是一種特殊的函數(shù)調(diào)用，是在一個函數(shù)中又調(diào)用了函數(shù)本身。遞歸程序的本質(zhì)是函數(shù)調(diào)用，而函數(shù)調(diào)用是要花費(fèi)額外的時間和空間。在系統(tǒng)內(nèi)部，函數(shù)調(diào)用是用棧來實(shí)現(xiàn)，如果程序員可以自己控制這個棧，就可以消除遞歸調(diào)用。36快速排序voidquicksort(inta[],intlow,inthigh){intmid;if(low>=high)return;mid=divide(a,low,high);quicksort(a,low,mid-1);quicksort(a,mid+1,high);}37快速排序的非遞歸實(shí)現(xiàn)設(shè)置一個棧，記錄要做的工作，即要排序的數(shù)據(jù)段先將整個數(shù)組進(jìn)棧當(dāng)排序區(qū)間被分成兩半時，把一半進(jìn)棧，先排序另一半。排完后再去檢查棧是否為空，為空，則排序結(jié)束，否則從棧中彈出一個區(qū)間，排序該區(qū)間。棧元素的格式：

structnode{intleft;intright;};3894183650941836startfinish5240986134mid20startfinish986134finishstart986134986431mid1039voidquicksort(inta[],intsize){seqStack<node>st;intmid,start,finish;nodes;if(size<=1)return;//排序整個數(shù)組

s.left=0;s.right=size-1;st.push(s);40while(!st.isEmpty()){s=st.pop();start=s.left;finish=s.right;mid=divide(a,start,finish);if(mid-start>1){s.left=start;s.right=mid-1;st.push(s);}if(finish-mid>1){s.left=mid+1;s.right=finish;st.push(s)；}}}41棧的應(yīng)用遞歸函數(shù)的非遞歸實(shí)現(xiàn)符號平衡檢查表達(dá)式的計算42括號配對檢查編譯程序的任務(wù)之一，就是檢查括號是否配對。如：括號(、[和{后面必須依次跟隨相應(yīng)的}、]及)，“后面必須有”。簡單地用開括號和閉括號的數(shù)量是否相等來判斷開括號與閉括號是否配對是不行的。例如，符號串[（）]是正確的，而符號串（[）]是不正確的。因?yàn)楫?dāng)遇到）那樣的閉括號時，它與最近遇到開括號匹配。43使用棧解決符號配對使用棧，遇到左括號進(jìn)棧，見到右括號，則出棧，并比較兩者是否配對。如判斷（3+（5-2）*（6+4）/2），（3+（（5-2）*（6+4）/2）

“abc”，‘n’

（a[3]+a[4]–‘a(chǎn)’）44算法首先創(chuàng)建一個空棧。從源程序中讀入符號。如果讀入的符號是開符號，那末就將其進(jìn)棧。如果讀入的符號是一個閉符號但棧是空的，出錯。否則，將棧中的符號出棧。如果出棧的符號和和讀入的閉符號不匹配，出錯。繼續(xù)從文件中讀入下一個符號，非空則轉(zhuǎn)向3，否則執(zhí)行7。如果棧非空，報告出錯，否則括號配對成功。45細(xì)節(jié)問題如果對C++的源程序使用此算法，需要考慮三種括號：圓括號、方括號和花括號。但有時又不需要考慮圓括號、花括號、方括號是否匹配的問題。例如，當(dāng)括號出現(xiàn)在注釋、字符串常量、字符常量中時，就不需要考慮它的匹配問題。在C++中有很多轉(zhuǎn)義字符，因此在讀入一個字符時，還必須考慮如何識別轉(zhuǎn)義字符。46要求設(shè)計一個類Balance：對象初始化時傳給它一個源文件名。這個類提供一個成員函數(shù)checkBalance檢查源文件中的符號是否配對。輸出所有不匹配的符號及所在的行號47類的定義classbalance{private: ifstreamfin;//待檢查的文件流

intcurrentLine;//正在處理行的的行號

intErrors;//已發(fā)現(xiàn)的錯誤數(shù)

structSymbol{charToken;intTheLine;};enumCommentType{SlashSlash,SlashStar};public: balance(constchar*s); intCheckBalance();48private：

boolCheckMatch(charSymb1,charSymb2,intLine1,intLine2);charGetNextSymbol();voidPutBackChar(charch);voidSkipComment(enumCommentTypetype);voidSkipQuote(chartype);charNextChar();};classnoFile{};49構(gòu)造函數(shù)balance::balance(constchar*s){fin.open(s);if(!fin)thrownoFile();currentLine=1;Errors=0;}50CheckBalance的實(shí)現(xiàn)檢查輸入流對象中的括號是否匹配，并返回錯誤數(shù)算法的實(shí)現(xiàn)需要用到一個棧，我們可以用本章中實(shí)現(xiàn)的棧類，如seqStack。采用逐步精細(xì)化的方法分解這個函數(shù)51自頂向下的分解初始化棧為空；While(lastChar=讀文件，直到讀入一括號)Switch(lastChar){case‘{‘,‘[‘,‘(‘：進(jìn)棧

case‘}’,’]’,’)’：

if(?？眨┹敵瞿承心撤柌黄ヅ?；出錯數(shù)加1;else{match=出棧的符號；檢查lastChar與match是否匹配；如不匹配，輸出出錯信息，出錯數(shù)加1；

}}if(棧非空)棧中元素均沒有找到匹配的閉符號，輸出這些錯誤

return出錯數(shù)52進(jìn)一步需要細(xì)化讀文件，直到讀入一括號；輸出某行某符號不匹配；出錯數(shù)加1；檢查lastChar與match是否匹配。如不匹配，輸出出錯信息，出錯數(shù)加1；棧中元素均沒有找到匹配的閉符號，輸出這些錯誤53進(jìn)一步抽取子函數(shù)第1項(xiàng)工作：GetNextSymbol功能：從文件的當(dāng)前位置開始，跳過所有的非括號，讀到第一個括號后返回。在遇到文件結(jié)束時，返回一個特定的符號，如NULL。函數(shù)原型：函數(shù)有一個字符型的返回值。執(zhí)行該函數(shù)必須有一個輸入流，在讀輸入流的過程中，當(dāng)前處理的行號會變，在讀的過程中也可能遇到異常情況，因此出錯數(shù)也會變。這三個信息：文件流對象，當(dāng)前處理的行號，出錯個數(shù)都是對象的數(shù)據(jù)成員。因此函數(shù)原型為：charGetNextSymbol（）。第3項(xiàng)工作：CheckMatch功能：比較兩個指定位置的待比較的符號是否匹配函數(shù)原型：boolbalance::CheckMatch(charSymb1,charSymb2,intLine1,intLine2)54CheckBalance的定義intbalance::CheckBalance(){structSymbolnode;seqStack<Symbol>st;charLastChar,Match;//LastChar為讀入的符號，Match為棧頂?shù)姆朇heckBalance函數(shù)不需要參數(shù)。因?yàn)檩斎肓鲗ο笫穷惖臄?shù)據(jù)成員。返回值是一個整型數(shù)，表示出錯個數(shù)55while(LastChar=GetNextSymbol()){switch(LastChar){ case'(':case'[':case'{':node.Token=LastChar;node.TheLine=currentLine;st.push(node);break; case')':case']':case'}': if(st.isEmpty()){Errors++; cout<<"在第"<<currentLine<<"有一個多余的"<<LastChar<<endl; }else{node=st.pop();Match=node.Token; if(!CheckMatch(Match,LastChar,node.TheLine,currentLine))++Errors; } break;} }56while(!st.isEmpty()){ Errors++; node=st.pop(); cout<<"第"<<node.TheLine<<"行的符號"<<node.Token<<"不匹配\n"; }returnErrors;}57CheckMatchboolbalance::CheckMatch(charSymb1,charSymb2,intLine1,intLine2){if(Symb1=='('&&Symb2!=')'||Symb1=='['&&Symb2!=']'||Symb1=='{'&&Symb2!='}'){ cout<<"發(fā)現(xiàn)第"<<Line2<<"的符號"<<Symb2<<"與第"<<Line1<<"的符號"<<Symb1<<"不匹配\n"; returnfalse; }elsereturntrue;}58GetNextSymbol在讀文件時要跳過其它符號，提取出各類括號注釋中的括號不用考慮，字符串常量和字符常量中的括號也不用考慮。C++中的注釋又有兩種形式。一種是以“//”開始到本行結(jié)束。另一種是以“/*”開始到“*/”結(jié)束，可以跨行。不管是哪一種注釋，都要判斷兩個符號才能決定59GetNextSymbol的偽代碼CharGetNextSymbol(){while(ch=從文件中讀入下一字符){ if(Ch==‘/’){//可能是注釋的開始

if(ch=從文件中讀入下一字符) if(Ch==‘*’)跳過標(biāo)準(zhǔn)C的注釋;elseif(Ch==‘/’)跳過C++的注釋; else不是注釋，把ch放回輸入流; }elseif(Ch==‘\’’||Ch==‘”’)跳過字符常量或字符串常量;elseif(Ch==‘{’||Ch==’[’||Ch==‘(’||Ch==’)’||Ch==‘]’||Ch==’}’)returnCh;}return0;//文件結(jié)束。}60進(jìn)一步提取子函數(shù)從文件中讀入下一字符：

charNextChar();跳過的注釋：voidSkipComment(enumCommentTypetype);把ch放回輸入流：

voidPutBackChar(charch);跳過字符常量或字符串常量：

voidSkipQuote(chartype);61GetNextSymbol函數(shù)的實(shí)現(xiàn)charbalance::GetNextSymbol(){charch;while(ch=NextChar()){ if(ch=='/'){ ch=NextChar(); if(ch=='*')SkipComment(SlashStar);elseif(ch=='/')SkipComment(SlashSlash); elsePutBackChar(ch); } elseif(ch=='\''||ch=='"')SkipQuote(ch); elseif(ch=='{'||ch=='['||ch=='('||ch==')'||ch==']'||ch=='}')returnch; } returnNULL;//文件結(jié)束。}62NextChar函數(shù)的實(shí)現(xiàn)NextChar函數(shù)從輸入文件流中讀入一個字符，返回給調(diào)用程序，遇到文件結(jié)束符，返回NULL。如遇到換行符，則當(dāng)前處理行加1。charbalance::NextChar(){charch;if((ch=fin.get())==EOF)returnNULL;if(ch=='\n')currentLine++;returnch;}63PutBackChar函數(shù)的實(shí)現(xiàn)PutBackChar函數(shù)將傳入的字符放回輸入流，這是通過調(diào)用輸入流對象的成員函數(shù)putback實(shí)現(xiàn)的。如放回的字符是回車，當(dāng)前處理行號減1。voidbalance::PutBackChar(charch){fin.putback(ch);if(ch=='\n')currentLine--;}64SkipQuote函數(shù)的實(shí)現(xiàn)讀文件，直到讀到一個和參數(shù)值相同的符號。要注意幾個特殊情況：字符或字符串常量是不允許跨行的。也就是說，如果在讀文件的過程中遇到了回車，則表示字符或字符串常量的開始和結(jié)束符不匹配，輸出出錯信息。在字符或字符串常量中可能會包含單引號或雙引號，此時不能將這個單引號或雙引號作為結(jié)束符。如何知道這個單引號或雙引號代表的是普通的字符而不是結(jié)束符呢？C++采用了轉(zhuǎn)義字符來表示，因此當(dāng)讀到一個表示轉(zhuǎn)義字符開始的標(biāo)記（\）時，不管它后面是什么符號，都不用檢查。65voidbalance::SkipQuote(chartype){charch;while((ch=NextChar())){if(ch==type)return;elseif(ch=='\n'){Errors++;cout<<"missingclosingquoteatline"<<currentLine<<endl;return;}elseif(ch=='\\')ch=NextChar();}}66SkipComment函數(shù)SkipComment有一個表示注釋類型的參數(shù)。該函數(shù)會根據(jù)不同的注釋類型完成跳過注釋的任務(wù)：如果是以“//”開頭的注釋，則不斷地讀文件直到遇到換行或文件結(jié)束符如果是以“/*”開頭的注釋，則必須讀到“*/”為止。在第二種注釋中，判斷注釋是否結(jié)束要判斷連續(xù)的兩個符號，因此用一個變量flag保存前一次讀到的符號。67SkipComment的偽代碼voidSkipComment(enumCommentTypetype){if(type==SlashSlash)

讀文件，直到遇到換行符或文件結(jié)束符，返回

flag=‘

‘;While(ch=從文件中讀入一符號){ If（flag=*&&ch=/）遇到的是“*/”，則注解被正常跳過了，返回。

flag=ch;}

沒有遇到“*/”，Errors++，輸出出錯信息}68SkipComment函數(shù)的實(shí)現(xiàn)voidbalance::SkipComment(enumCommentTypetype){charch,flag;if(type==SlashSlash){ while((ch=NextChar())&&(ch!='\n')); return;}//處理/*...*/的情況

flag='';while((ch=NextChar())!=NULL){ if(flag=='*'&&ch=='/')return; flag=ch; }Errors++;cout<<"Commentisunterminated!"<<endl;}69balance類的使用設(shè)計一程序，利用balance類檢查源文件中的括號是否配對。它有兩種執(zhí)行方式：程序運(yùn)行后，用戶通過鍵盤輸入要檢查的文件名；將要檢查的源文件名作為命令行的參數(shù)，程序依次對這些參數(shù)構(gòu)造balance類的對象，檢查它們中的括號配對情況。70#include<iostream>usingnamespacestd;#include"balance.h"intmain(intargc,constchar**argv){charfilename[80];balance*p;intresult;try{if(argc==1){ cout<<"請輸入文件名:";cin>>filename; p=newbalance(filename); result=p->CheckBalance();deletep; cout<<"共"<<result<<"個錯"<<endl; return0;}while(--argc){ cout<<"檢查文件"<<*++argv<<endl; p=newbalance(*argv); result=p->CheckBalance();deletep; cout<<"共"<<result<<"個錯"<<endl; }}catch(noFile){cout<<"nosuchfile"<<endl;}return0;}71棧的應(yīng)用遞歸函數(shù)的非遞歸實(shí)現(xiàn)符號平衡檢查表達(dá)式的計算72中綴式和后綴式對于一個表達(dá)式a+b

前綴式：+ab波蘭式中綴式：a+b

后綴式：ab+逆波蘭式73后綴式的優(yōu)點(diǎn)可以不考慮運(yùn)算符的優(yōu)先級例如：(a+b)*c/(d-e)后綴式為：ab+c*de-/74一個后綴式是如何工作的？初始化一個棧。依次讀入后綴式的操作數(shù)和運(yùn)算符。若讀到的是操作數(shù)，則將其進(jìn)棧。若讀到的是運(yùn)算符，則將棧頂?shù)膬蓚€操作數(shù)出棧，后彈出的操作數(shù)為被操作數(shù)，先彈出的為操作數(shù)，將得到的操作數(shù)完成運(yùn)算符所規(guī)定的運(yùn)算，并將結(jié)果進(jìn)棧?；氐?的讀入操作，繼續(xù)。當(dāng)棧中只剩有一個操作數(shù)時，彈出該操作數(shù)，它就是表達(dá)式的值。75以表達(dá)式5*(7-2*3)+8/2為例，

它的后綴式為5

7

2

3*-*8

2/+

步驟讀剩的后綴式棧中內(nèi)容步驟讀剩的后綴式棧中內(nèi)容15

7

2

3*-*8

2/+10/+5

8

227

2

3*-*8

2/+511+5

432

3*-*8

2/+5

712943*-*8

2/+5

7

2135*-*8

2/+5

7

2

3146-*8

2/+5

7

6157*8

2/+5

11688

2/+51792/+5

81876中綴式轉(zhuǎn)換為后綴式的算法若讀入的是操作數(shù)，立即輸出。若讀入的是閉括號，則將棧中的運(yùn)算符依次出棧，并將其放在操作數(shù)序列之后。出棧操作一直進(jìn)行到遇到相應(yīng)的開括號為止。將開括號出棧。若讀入的是開括號，則進(jìn)棧。若讀入的是運(yùn)算符，如果棧頂運(yùn)算符優(yōu)先級高，則棧頂運(yùn)算符出棧；出棧操作一直要進(jìn)行到棧頂運(yùn)算符優(yōu)先級低為止，然后將新讀入的運(yùn)算符進(jìn)棧保存。在讀入操作結(jié)束時，將棧中所有的剩余運(yùn)算符依次出棧，并放在操作數(shù)序列之后，直至棧空為止。77序號讀剩的表達(dá)式棧輸出1(5+6*(7+3)/3)/4+525+6*(7+3)/3)/4+5(3+6*(7+3)/3)/4+5(546*(7+3)/3)/4+5(+55*(7+3)/3)/4+5(+5667+3)/3)/4+5(+*(567+3)/3)/4+5(+*(56783)/3)/4+5(+*(+5679)/3)/4+5(+*(+567310/3)/4+5(+5673+*113)/4+5(+/5673+*12)/4+5(+/5673+*313/4+55673+*3/+144+5/5673+*3/+15+5/5673+*3/+4165+5673+*3/+4/17+5673+*3/+4/5185673+*3/+4/5+78簡單計算器的實(shí)現(xiàn)輸入一個中綴表達(dá)式,計算的對象為類型為int的正整數(shù)，能計算加、減、乘、除和乘方運(yùn)算，允許用括號改變優(yōu)先級。79設(shè)計思想按照面向?qū)ο蟮脑O(shè)計思想，先設(shè)計一個工具該工具可以保存一個表達(dá)式，并告訴表達(dá)式的計算結(jié)果?？梢噪S時改變工具中保存的表達(dá)式，就可得到不同的表達(dá)式的計算結(jié)果80

簡單計算器的主程序

intmain(){calcexp("3*(7+5)/6-2");cout<<exp.result()<<endl;exp="3*7+5";cout<<exp.result()<<endl;return0;}如有一個名為calc的類，則表達(dá)式的計算可用下列簡單的過程81calc類的設(shè)計數(shù)據(jù)成員：一個字符串，用于保存表達(dá)式公有成員函數(shù)：構(gòu)造和析構(gòu)函數(shù)計算表達(dá)式結(jié)果賦值運(yùn)算符重載82calc類的定義classcalc{ char*expression; enumtoken{OPAREN,ADD,SUB,MULTI,DIV,EXP,CPAREN,VALUE,EOL};voidBinaryOp(tokenop,seqStack<int>&dataStack); tokengetOp(int&value);public: calc(char*s){expression=newchar[strlen(s)+1];strcpy(expression,s);} ~calc(){deleteexpression;} intresult();};83計算器中的表達(dá)式的特點(diǎn)計算器中的表達(dá)式中的運(yùn)算數(shù)都是常量，因此當(dāng)發(fā)現(xiàn)某個運(yùn)算符可以運(yùn)算時，可以直接執(zhí)行運(yùn)算，保存運(yùn)算結(jié)果，而沒有必要寫出它的后綴表達(dá)式。即可以將轉(zhuǎn)換和計算兩個步驟合并起來，邊轉(zhuǎn)換邊計算。運(yùn)算過程需要用到兩個棧：中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式時的運(yùn)算符棧，執(zhí)行后綴表達(dá)式運(yùn)算時的運(yùn)算數(shù)棧。841(5+6*(7+3)/3)/4+525+6*(7+3)/3)/4+5(3+6*(7+3)/3)/4+5(546*(7+3)/3)/4+5(+55*(7+3)/3)/4+5(+5667+3)/3)/4+5(+*(567+3)/3)/4+5(+*(56783)/3)/4+5(+*(+5679)/3)/4+5(+*(+567310)/3)/4+5(+*(561011/3)/4+5(+560123)/4+5(+/56013)/4+5(+/560314/4+5(+52015/4+525164+5/2517+5/254185+6.2519+6.2552011.25更直接的一種方法85Result的偽代碼intcalc::result(){依次從表達(dá)式中取出一個合法的符號，直到表達(dá)式結(jié)束；

{switch(當(dāng)前符號) {case數(shù)字：將數(shù)字存入運(yùn)算數(shù)棧；

case‘(’:開括號進(jìn)運(yùn)算符棧;case‘)’:開括號和閉括號之間的所有運(yùn)算都可進(jìn)行，即將運(yùn)算符棧中的運(yùn)算符依次出棧，執(zhí)行相應(yīng)的運(yùn)算，直到‘（’出棧；

case‘^’:乘方運(yùn)算符進(jìn)運(yùn)算符棧；

case‘*’:case‘/’:運(yùn)算符棧中的/，*，^退棧執(zhí)行，當(dāng)前運(yùn)算符進(jìn)棧；

case‘+’:case‘-’:運(yùn)算符棧中的運(yùn)算符依次出棧執(zhí)行，直到棧為空或遇到開括號。當(dāng)前運(yùn)算符進(jìn)棧；

}}86運(yùn)算符棧中在所有的運(yùn)算符出棧執(zhí)行；if(運(yùn)算數(shù)棧為空）出錯，無運(yùn)算結(jié)果；result_value=運(yùn)算數(shù)棧出棧元素；if（運(yùn)算數(shù)棧非空）出錯，缺運(yùn)算符；returnresult_value;}87進(jìn)一步細(xì)化在上述偽代碼中，大多數(shù)的操作都是進(jìn)棧出棧，這些操作在棧類中都已實(shí)現(xiàn)。除此之外，還有兩個操作需要細(xì)化：從表達(dá)式中取出一個合法的符號

tokengetOp(int&value);執(zhí)行一個算術(shù)運(yùn)算

voidBinaryOp(tokenop,seqStack<int>&dataStack)；88result函數(shù)的實(shí)現(xiàn)intcalc::result(){tokenlastOp,topOp;intresult_value,CurrentValue;seqStack<token>opStack;seqStack<int>dataStack;char*str=expression;89while(true){ lastOp=getOp(CurrentValue); if(lastOp==EOL)break; switch(lastOp){caseVALUE:dataStack.push(CurrentValue);break;caseCPAREN:while(!opStack.isEmpty()&&(topOp=opStack.pop())!=OPAREN)BinaryOp(topOp,dataStack);if(topOp!=OPAREN)cerr<<"缺左括號!"<<endl; break;caseOPAREN:opStack.push(OPAREN);break; caseEXP:opStack.push(EXP);break; caseMULTI:caseDIV: while(!opStack.isEmpty()&&opStack.top()>=MULTI)BinaryOp(opStack.pop(),dataStack); opStack.push(lastOp); break; caseADD:caseSUB: while(!opStack.isEmpty()&