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

1第三章棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類(lèi)的實(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)個(gè)數(shù)為零時(shí)5棧的運(yùn)算創(chuàng)建一個(gè)棧create()：創(chuàng)建一個(gè)空的棧；進(jìn)棧push(x)：將x插入棧中，使之成為棧頂元素；出棧pop()：刪除棧頂元素并返回棧頂元素值；讀棧頂元素top()：返回棧頂元素值但不刪除棧頂元素；判棧空isEmpty()：若棧為空，返回true，否則返回false。6棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類(lèi)的實(shí)現(xiàn)STL中的棧棧的應(yīng)用7棧的順序?qū)崿F(xiàn)用連續(xù)的空間存儲(chǔ)棧中的結(jié)點(diǎn)，即數(shù)組進(jìn)棧和出棧總是在棧頂一端進(jìn)行，不會(huì)引起類(lèi)似順序表中的大量數(shù)據(jù)的移動(dòng)。用數(shù)組的后端表示棧頂。an…a1a0top_p棧底maxSizeelem8順序存儲(chǔ)時(shí)的運(yùn)算實(shí)現(xiàn)create()：按照用戶估計(jì)的棧的規(guī)模申請(qǐng)一個(gè)動(dòng)態(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類(lèi)似，只是不需要將top_p減1。isEmpty()：若top_p的值為-1，返回true，否則返回false。9順序?qū)崿F(xiàn)性能分析除了進(jìn)棧操作以外，所有運(yùn)算實(shí)現(xiàn)的時(shí)間復(fù)雜度都是O（1）。進(jìn)棧運(yùn)算在最壞情況下的時(shí)間復(fù)雜度是O（N）。但最壞情況在N次進(jìn)棧操作中至多出現(xiàn)一次。如果把擴(kuò)展數(shù)組規(guī)模所需的時(shí)間均攤到每個(gè)插入操作，每個(gè)插入只多了一個(gè)拷貝操作，因此從平均的意義上講，插入運(yùn)算還是常量的時(shí)間復(fù)雜度。這種分析方法稱(chēng)為均攤分析法。10棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類(lèi)的實(shí)現(xiàn)STL中的棧棧的應(yīng)用11棧的鏈接實(shí)現(xiàn)棧的操作都是在棧頂進(jìn)行的，不需要找某一元素的直接前驅(qū)的操作，因此不需要雙鏈表，用單鏈表就足夠了，而且不需要頭結(jié)點(diǎn)對(duì)棧來(lái)講，只需要考慮棧頂元素的插入刪除。從棧的基本運(yùn)算的實(shí)現(xiàn)方便性考慮，可將單鏈表的頭指針指向棧頂。12棧的鏈接實(shí)現(xiàn)an-1an-2a0…∧top_p13鏈接存儲(chǔ)時(shí)的運(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鏈接存儲(chǔ)時(shí)的運(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鏈接存儲(chǔ)時(shí)的運(yùn)算實(shí)現(xiàn)top()：返回top_p指向的結(jié)點(diǎn)的值。isEmpty()：若top_p的值為空指針，返回true，否則返回false。16鏈接棧的性能分析由于所有的操作都是對(duì)棧頂?shù)牟僮?，郵展中的元素個(gè)數(shù)無(wú)關(guān)。所以，所有運(yùn)算的時(shí)間復(fù)雜度都是O（1）17棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類(lèi)的實(shí)現(xiàn)STL中的棧棧的應(yīng)用18棧的抽象類(lèi)template<classelemType>classstack{public: virtualboolisEmpty()const=0; virtualvoidpush(constelemType&x)=0; virtualelemTypepop()=0;virtualelemTypetop()const=0; virtual~stack(){}};19順序棧類(lèi)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鏈接棧類(lèi)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)棧類(lèi)的實(shí)現(xiàn)STL中的棧棧的應(yīng)用27STL中的棧棧本質(zhì)上是一個(gè)線性表，在STL中棧類(lèi)是借助于線性表類(lèi)實(shí)現(xiàn)的。STL中的棧提供四個(gè)標(biāo)準(zhǔn)運(yùn)算：push、pop、top和empty。在STL中，借助于其他容器存儲(chǔ)數(shù)據(jù)的容器稱(chēng)為容器適配器。棧就是一個(gè)容器適配器28棧的類(lèi)模板定義一個(gè)棧對(duì)象要指明棧中元素的類(lèi)型以及借助于哪一個(gè)容器，因此棧的類(lèi)模板有兩個(gè)模板參數(shù)：棧元素類(lèi)型和所借助的容器類(lèi)型。?？梢越柚娜萜饔衯ector,list和deque。棧的類(lèi)模板的第二個(gè)參數(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)棧類(lèi)的實(shí)現(xiàn)STL中的棧棧的應(yīng)用31棧的應(yīng)用遞歸函數(shù)的非遞歸實(shí)現(xiàn)符號(hào)平衡檢查表達(dá)式的計(jì)算32棧的應(yīng)用—遞歸函數(shù)的非遞歸實(shí)現(xiàn)遞歸的本質(zhì)是函數(shù)調(diào)用，而函數(shù)調(diào)用是通過(guò)棧實(shí)現(xiàn)的。因此，遞歸可以用棧消除。voidf1(){…r1:f2();r2:…}voidf2(){…t1:f3();t2:…}voidf3(){……}33函數(shù)執(zhí)行過(guò)程f1f2f3r1t1r2t234函數(shù)調(diào)用的實(shí)現(xiàn)設(shè)置一個(gè)棧模擬函數(shù)調(diào)用。當(dāng)發(fā)生函數(shù)調(diào)用時(shí)，將當(dāng)前的函數(shù)的現(xiàn)場(chǎng)進(jìn)棧。調(diào)用f2前Top調(diào)用f2后Topr2調(diào)用f3后Topr2t2返回f2后Topr2返回f1后Top35遞歸遞歸是一種特殊的函數(shù)調(diào)用，是在一個(gè)函數(shù)中又調(diào)用了函數(shù)本身。遞歸程序的本質(zhì)是函數(shù)調(diào)用，而函數(shù)調(diào)用是要花費(fèi)額外的時(shí)間和空間。在系統(tǒng)內(nèi)部，函數(shù)調(diào)用是用棧來(lái)實(shí)現(xiàn)，如果程序員可以自己控制這個(gè)棧，就可以消除遞歸調(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è)置一個(gè)棧，記錄要做的工作，即要排序的數(shù)據(jù)段先將整個(gè)數(shù)組進(jìn)棧當(dāng)排序區(qū)間被分成兩半時(shí)，把一半進(jìn)棧，先排序另一半。排完后再去檢查棧是否為空，為空，則排序結(jié)束，否則從棧中彈出一個(gè)區(qū)間，排序該區(qū)間。棧元素的格式：

structnode{intleft;intright;};3894183650941836startfinish5240986134mid20startfinish986134finishstart986134986431mid1039voidquicksort(inta[],intsize){seqStack<node>st;intmid,start,finish;nodes;if(size<=1)return;//排序整個(gè)數(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)符號(hào)平衡檢查表達(dá)式的計(jì)算42括號(hào)配對(duì)檢查編譯程序的任務(wù)之一，就是檢查括號(hào)是否配對(duì)。如：括號(hào)(、[和{后面必須依次跟隨相應(yīng)的}、]及)，“后面必須有”。簡(jiǎn)單地用開(kāi)括號(hào)和閉括號(hào)的數(shù)量是否相等來(lái)判斷開(kāi)括號(hào)與閉括號(hào)是否配對(duì)是不行的。例如，符號(hào)串[（）]是正確的，而符號(hào)串（[）]是不正確的。因?yàn)楫?dāng)遇到）那樣的閉括號(hào)時(shí)，它與最近遇到開(kāi)括號(hào)匹配。43使用棧解決符號(hào)配對(duì)使用棧，遇到左括號(hào)進(jìn)棧，見(jiàn)到右括號(hào)，則出棧，并比較兩者是否配對(duì)。如判斷（3+（5-2）*（6+4）/2），（3+（（5-2）*（6+4）/2）

“abc”，‘n’

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

intcurrentLine;//正在處理行的的行號(hào)

intErrors;//已發(fā)現(xiàn)的錯(cuò)誤數(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)檢查輸入流對(duì)象中的括號(hào)是否匹配，并返回錯(cuò)誤數(shù)算法的實(shí)現(xiàn)需要用到一個(gè)棧，我們可以用本章中實(shí)現(xiàn)的棧類(lèi)，如seqStack。采用逐步精細(xì)化的方法分解這個(gè)函數(shù)51自頂向下的分解初始化棧為空；While(lastChar=讀文件，直到讀入一括號(hào))Switch(lastChar){case‘{‘,‘[‘,‘(‘：進(jìn)棧

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

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

}}if(棧非空)棧中元素均沒(méi)有找到匹配的閉符號(hào)，輸出這些錯(cuò)誤

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

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

charNextChar();跳過(guò)的注釋?zhuān)簐oidSkipComment(enumCommentTypetype);把ch放回輸入流：

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

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ù)從輸入文件流中讀入一個(gè)字符，返回給調(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ù)將傳入的字符放回輸入流，這是通過(guò)調(diào)用輸入流對(duì)象的成員函數(shù)putback實(shí)現(xiàn)的。如放回的字符是回車(chē)，當(dāng)前處理行號(hào)減1。voidbalance::PutBackChar(charch){fin.putback(ch);if(ch=='\n')currentLine--;}64SkipQuote函數(shù)的實(shí)現(xiàn)讀文件，直到讀到一個(gè)和參數(shù)值相同的符號(hào)。要注意幾個(gè)特殊情況：字符或字符串常量是不允許跨行的。也就是說(shuō)，如果在讀文件的過(guò)程中遇到了回車(chē)，則表示字符或字符串常量的開(kāi)始和結(jié)束符不匹配，輸出出錯(cuò)信息。在字符或字符串常量中可能會(huì)包含單引號(hào)或雙引號(hào)，此時(shí)不能將這個(gè)單引號(hào)或雙引號(hào)作為結(jié)束符。如何知道這個(gè)單引號(hào)或雙引號(hào)代表的是普通的字符而不是結(jié)束符呢？C++采用了轉(zhuǎn)義字符來(lái)表示，因此當(dāng)讀到一個(gè)表示轉(zhuǎn)義字符開(kāi)始的標(biāo)記（\）時(shí)，不管它后面是什么符號(hà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有一個(gè)表示注釋類(lèi)型的參數(shù)。該函數(shù)會(huì)根據(jù)不同的注釋類(lèi)型完成跳過(guò)注釋的任務(wù)：如果是以“//”開(kāi)頭的注釋?zhuān)瑒t不斷地讀文件直到遇到換行或文件結(jié)束符如果是以“/*”開(kāi)頭的注釋?zhuān)瑒t必須讀到“*/”為止。在第二種注釋中，判斷注釋是否結(jié)束要判斷連續(xù)的兩個(gè)符號(hào)，因此用一個(gè)變量flag保存前一次讀到的符號(hào)。67SkipComment的偽代碼voidSkipComment(enumCommentTypetype){if(type==SlashSlash)

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

flag=‘

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

flag=ch;}

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

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

后綴式：ab+逆波蘭式73后綴式的優(yōu)點(diǎn)可以不考慮運(yùn)算符的優(yōu)先級(jí)例如：(a+b)*c/(d-e)后綴式為：ab+c*de-/74一個(gè)后綴式是如何工作的？初始化一個(gè)棧。依次讀入后綴式的操作數(shù)和運(yùn)算符。若讀到的是操作數(shù)，則將其進(jìn)棧。若讀到的是運(yùn)算符，則將棧頂?shù)膬蓚€(gè)操作數(shù)出棧，后彈出的操作數(shù)為被操作數(shù)，先彈出的為操作數(shù)，將得到的操作數(shù)完成運(yùn)算符所規(guī)定的運(yùn)算，并將結(jié)果進(jìn)棧。回到2的讀入操作，繼續(xù)。當(dāng)棧中只剩有一個(gè)操作數(shù)時(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ù)，立即輸出。若讀入的是閉括號(hào)，則將棧中的運(yùn)算符依次出棧，并將其放在操作數(shù)序列之后。出棧操作一直進(jìn)行到遇到相應(yīng)的開(kāi)括號(hào)為止。將開(kāi)括號(hào)出棧。若讀入的是開(kāi)括號(hào)，則進(jìn)棧。若讀入的是運(yùn)算符，如果棧頂運(yùn)算符優(yōu)先級(jí)高，則棧頂運(yùn)算符出棧；出棧操作一直要進(jìn)行到棧頂運(yùn)算符優(yōu)先級(jí)低為止，然后將新讀入的運(yùn)算符進(jìn)棧保存。在讀入操作結(jié)束時(shí)，將棧中所有的剩余運(yùn)算符依次出棧，并放在操作數(shù)序列之后，直至?？諡橹?。77序號(hào)讀剩的表達(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簡(jiǎn)單計(jì)算器的實(shí)現(xiàn)輸入一個(gè)中綴表達(dá)式,計(jì)算的對(duì)象為類(lèi)型為int的正整數(shù)，能計(jì)算加、減、乘、除和乘方運(yùn)算，允許用括號(hào)改變優(yōu)先級(jí)。79設(shè)計(jì)思想按照面向?qū)ο蟮脑O(shè)計(jì)思想，先設(shè)計(jì)一個(gè)工具該工具可以保存一個(gè)表達(dá)式，并告訴表達(dá)式的計(jì)算結(jié)果。可以隨時(shí)改變工具中保存的表達(dá)式，就可得到不同的表達(dá)式的計(jì)算結(jié)果80

簡(jiǎn)單計(jì)算器的主程序

intmain(){calcexp("3*(7+5)/6-2");cout<<exp.result()<<endl;exp="3*7+5";cout<<exp.result()<<endl;return0;}如有一個(gè)名為calc的類(lèi)，則表達(dá)式的計(jì)算可用下列簡(jiǎn)單的過(guò)程81calc類(lèi)的設(shè)計(jì)數(shù)據(jù)成員：一個(gè)字符串，用于保存表達(dá)式公有成員函數(shù)：構(gòu)造和析構(gòu)函數(shù)計(jì)算表達(dá)式結(jié)果賦值運(yùn)算符重載82calc類(lèi)的定義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計(jì)算器中的表達(dá)式的特點(diǎn)計(jì)算器中的表達(dá)式中的運(yùn)算數(shù)都是常量，因此當(dāng)發(fā)現(xiàn)某個(gè)運(yùn)算符可以運(yùn)算時(shí)，可以直接執(zhí)行運(yùn)算，保存運(yùn)算結(jié)果，而沒(méi)有必要寫(xiě)出它的后綴表達(dá)式。即可以將轉(zhuǎn)換和計(jì)算兩個(gè)步驟合并起來(lái)，邊轉(zhuǎn)換邊計(jì)算。運(yùn)算過(guò)程需要用到兩個(gè)棧：中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式時(shí)的運(yùn)算符棧，執(zhí)行后綴表達(dá)式運(yùn)算時(shí)的運(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á)式中取出一個(gè)合法的符號(hào)，直到表達(dá)式結(jié)束；

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

case‘(’:開(kāi)括號(hào)進(jìn)運(yùn)算符棧;case‘)’:開(kāi)括號(hào)和閉括號(hào)之間的所有運(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í)行，直到棧為空或遇到開(kāi)括號(hào)。當(dāng)前運(yùn)算符進(jìn)棧；

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

tokengetOp(int&value);執(zhí)行一個(gè)算術(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<<"缺左括號(hào)!"<<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()&