數(shù)據(jù)結(jié)構(gòu)第3章

數(shù)據(jù)結(jié)構(gòu)A·第3章第3章堆棧和隊(duì)列

引言堆棧和隊(duì)列也是最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，在算法設(shè)計(jì)中經(jīng)常使用，它們?cè)谶壿嬌贤€性表一樣，都是線性結(jié)構(gòu)，差別在于：線性表可以在表的任意位置插入和刪除元素，而堆棧和隊(duì)列只能在表的端點(diǎn)插入和刪除元素。第3章堆棧和隊(duì)列內(nèi)容提要

1、定義堆棧與隊(duì)列抽象數(shù)據(jù)類型

2、討論堆棧與隊(duì)列的順序表示方法

3、討論堆棧與隊(duì)列的鏈接表示方法

4、以表達(dá)式計(jì)算為例討論堆棧的應(yīng)用

5、介紹遞歸的概念和遞歸算法3.1堆棧a0a1…ai…an-1入棧出棧bottomtop

圖3-1棧的示意圖堆棧（簡(jiǎn)稱棧）的示意圖S=(a0,a1,…,an-1)課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列3.3表達(dá)式的計(jì)算3.4遞歸3.1堆棧3.1.1堆棧抽象數(shù)據(jù)類型

堆棧是后進(jìn)先出（LastInFirstOut——LIFO）的動(dòng)態(tài)線性數(shù)據(jù)結(jié)構(gòu)。

1.堆棧的定義堆棧工作的演示ACB3.1堆棧3.1.1堆棧抽象數(shù)據(jù)類型

同時(shí)，堆棧也是是后進(jìn)先出（LastInFirstOut——LIFO）的動(dòng)態(tài)線性數(shù)據(jù)結(jié)構(gòu)。

1.堆棧的定義ACB堆棧工作的演示3.1堆棧3.1.1堆棧抽象數(shù)據(jù)類型

ADTStack{數(shù)據(jù):0個(gè)或多個(gè)元素的線性序列（a0,a1,...,an-1),其最大允許長(zhǎng)度為ＭaxStackSize。其插入和刪除運(yùn)算都限制在同一端進(jìn)行，并遵循LIFO原則。運(yùn)算:Create()：建立一個(gè)空棧。

Destroy()：撤消一個(gè)棧。

IsEmpty()：若?？?，則返回true;否則返回false。

IsFull()：若棧滿，則返回true;否則返回false。

Top(x)：返回棧頂元素。若操作成功，則返回true;否則返回false。

Push(x)：在棧頂插入元素x。

Pop()：從棧中刪除棧頂元素。

Clear():清除堆棧中全部元素。}

2.棧的抽象數(shù)據(jù)類型3.1堆棧3.1.1堆棧抽象數(shù)據(jù)類型

3.棧的C++模板抽象類程序3-1堆棧的C++類#include<iostream.h>template<classT>classStack{public:virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualboolTop(T&x)const=0;virtualboolPush(Tx)=0;virtualboolPop()=0;virtualvoidClear()=0;};3.1堆棧3.1.2棧的順序表示

1.棧的順序表示法an-1a1a0topn-110棧s圖3-2順序棧maxTop………一維數(shù)組s存儲(chǔ)棧中元素，maxTop+1為最大允許容量，top指示棧頂，top==-1表示空棧,top==maxTop表示棧滿。

S=(a0,a1,…,an-1)3.1堆棧3.1.2棧的順序表示

2.順序棧類template<classT>classSeqStack:publicStack<T>{public:SeqStack(intmSize);~SeqStack(){delete[]s;}boolIsEmpty()const{return(top==-1);}boolIsFull()const{return(top==MaxTop);}boolTop(T&x)const;boolPush(Tx);boolPop();voidClear(){top=-1;}private:inttop;//總是指向棧頂元素

intmaxTop;T*s;}an-1a1a0topn-110棧s圖3-2順序棧maxTop………3.1堆棧3.1.2棧的順序表示

3.動(dòng)態(tài)一維數(shù)組描述順序棧類an-1a1a0topn-110棧s圖3-2順序棧maxTop………template<classT>classSeqStack:publicStack<T>{public:……private:intmaxTop;inttop;T*s;}3.1堆棧3.1.2棧的順序表示

3.動(dòng)態(tài)一維數(shù)組描述順序棧類an-1a1a0topn-110棧s圖3-2順序棧maxTop………構(gòu)造函數(shù)template<classT>SeqStack<T>::SeqStack(intmSize){maxTop=mSize-1;s=newT[mSize];top=-1;}析構(gòu)函數(shù)SeqStack<T>::~SeqStack(intMaxSize){delete[]s;}3.1堆棧3.1.2棧的順序表示

4.在順序存儲(chǔ)表示下實(shí)現(xiàn)棧上定義的操作an-1a1a0topn-110棧s圖3-2順序棧maxTop………（1）取棧頂元素template<classT>boolSeqStack<T>::Top(T&x)const{if(IsEmpty()){//空棧處理

cout<<"Empty"<<endl;returnfalse;}x=s[top];returntrue;}3.1堆棧3.1.2棧的順序表示

4.在順序存儲(chǔ)表示下實(shí)現(xiàn)棧上定義的操作an-1a1a0topn-110棧s圖3-2順序棧maxTop………（2）進(jìn)棧（壓入）template<classT>boolSeqStack<T>::Push(T&x){if(IsFull()){//溢出處理

cout<<"Overflow"<<endl;returnfalse;}s[++top]=x;returntrue;}3.1堆棧3.1.2棧的順序表示

4.在順序存儲(chǔ)表示下實(shí)現(xiàn)棧上定義的操作an-1a1a0topn-110棧s圖3-2順序棧maxTop………（3）出棧（彈出）template<classT>boolSeqStack<T>::Pop(){if(IsEmpty()){//空棧處理

cout<<"Underflow"<<endl;returnfalse;}top--;returntrue;}3.1堆棧3.1.3棧的鏈接表示

1.棧的鏈接表示法（鏈?zhǔn)綏＃╂準(zhǔn)綏５亩x和操作的實(shí)現(xiàn)類似于單鏈表。an-1a0…top∧圖3-3鏈?zhǔn)綏?/p>

an-2an-3不帶表頭結(jié)點(diǎn)的單鏈表課堂提要第3章堆棧和隊(duì)列3.1堆棧

3.1.1棧抽象數(shù)據(jù)類型

3.1.2棧的順序表示

3.1.3棧的鏈接表示3.2隊(duì)列3.3表達(dá)式的計(jì)算3.4遞歸3.1堆棧3.1.3棧的鏈接表示

2.在鏈接表示下實(shí)現(xiàn)棧上定義的操作an-1a0…top∧圖3-3鏈?zhǔn)綏?/p>

an-2an-3入棧操作push(Tx)Node<T>*q=newNode<T>;q->element=x;q->link=top;top=q;3.1堆棧3.1.3棧的鏈接表示

2.在鏈接表示下實(shí)現(xiàn)棧上定義的操作an-1a0…top∧圖3-3鏈?zhǔn)綏?/p>

an-2an-3出棧操作Pop()Node<T>*q=top;top=top->link;deleteq;3.2隊(duì)列3.1.3棧的鏈接表示課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列

3.2.1隊(duì)列抽象數(shù)據(jù)類型

3.2.2隊(duì)列的順序表示

3.2.3隊(duì)列的鏈接表示3.3表達(dá)式的計(jì)算3.4遞歸隊(duì)列的示意圖

Q=(a0,a1,…,an-1)a0a1…an-1frontrear入隊(duì)出隊(duì)3.2隊(duì)列3.2.1隊(duì)列抽象數(shù)據(jù)類型

1.隊(duì)列的定義隊(duì)列是限定在表的一端插入，在表的另一端刪除的線性數(shù)據(jù)結(jié)構(gòu)。若隊(duì)列中無(wú)元素，則為空隊(duì)列隊(duì)尾——允許插入元素的一端隊(duì)頭——允許刪除元素的另一端Q=(a0,a1,…,an-1)課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列

3.2.1隊(duì)列抽象數(shù)據(jù)類型

3.2.2隊(duì)列的順序表示

3.2.3隊(duì)列的鏈接表示3.3表達(dá)式的計(jì)算3.4遞歸3.2隊(duì)列3.2.1隊(duì)列抽象數(shù)據(jù)類型

1.隊(duì)列的定義a0a1…an-1frontrear入隊(duì)出隊(duì)若給定隊(duì)列Q=(a0,a1,…,an-1)，則稱a0是隊(duì)頭元素，an-1是隊(duì)尾元素。元素a0,…,an-1依次入隊(duì)，出隊(duì)的順序與入隊(duì)相同，a0出隊(duì)后，a1才能出隊(duì)，因此又稱隊(duì)列為先進(jìn)先出（FirstInFirstOut——FIFO）的動(dòng)態(tài)線性數(shù)據(jù)結(jié)構(gòu)。3.2隊(duì)列3.2.1隊(duì)列抽象數(shù)據(jù)類型

1.隊(duì)列的定義ACBrearfront隊(duì)列工作的演示(入隊(duì))3.2隊(duì)列3.2.1隊(duì)列抽象數(shù)據(jù)類型

1.隊(duì)列的定義rearfront隊(duì)列工作的演示(出隊(duì))ACB3.2隊(duì)列3.2.1隊(duì)列抽象數(shù)據(jù)類型

2.隊(duì)列的抽象數(shù)據(jù)類型ADTQueue{

數(shù)據(jù):0個(gè)或多個(gè)元素的線性序列（a0,a1,…,an-1),其最大長(zhǎng)度為MaxQueueSize。它插入在一端進(jìn)行，而刪除在另一端進(jìn)行，并遵循FIFO原則。運(yùn)算:Create()：建立一個(gè)空隊(duì)列。

Destroy()：撤消一個(gè)隊(duì)列。

IsEmpty()：若隊(duì)列空，則返回true;否則返回false。

IsFull()：若隊(duì)列滿，則返回true;否則返回false。

Front(x)：在x中返回隊(duì)頭元素。操作成功返回true；否則返回false。

EnQueue(x)：在隊(duì)尾插入元素x。操作成功返回true；否則返回false。

DeQueue()：從隊(duì)列中刪除隊(duì)頭元素。操作成功返回true；否則返回falseClear():清除隊(duì)列中全部元素。}3.2隊(duì)列3.2.1隊(duì)列抽象數(shù)據(jù)類型

3.隊(duì)列的C++模板抽象類template<classT>classQueue{public:Queue(){};~Queue(){}; virtualboolEnQueue(constTx)=0;virtualboolDeQueue()=0;virtualboolFront(T&x)=0; virtualboolIsEmpty()const=0; virtualboolIsFull()const=0;virtualvoidClear()=0; };3.2隊(duì)列3.2.2隊(duì)列的順序表示

1.隊(duì)列的順序表示法課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列

3.2.1隊(duì)列抽象數(shù)據(jù)類型

3.2.2隊(duì)列的順序表示

3.2.3隊(duì)列的鏈接表示3.3表達(dá)式的計(jì)算3.4遞歸01234=maxSize-1(a)空隊(duì)列fr

圖中f為front,r為rear3.2隊(duì)列3.2.2隊(duì)列的順序表示

1.隊(duì)列的順序表示法

從(d)可以看到，當(dāng)再有元素需要入隊(duì)時(shí)將產(chǎn)生“溢出”，然而隊(duì)列中尚有三個(gè)空元素單元，我們稱這種現(xiàn)象為“假溢出”。指針f指向隊(duì)首元素的前一個(gè)位置，指針r指向隊(duì)尾元素50403020(b)元素20，30，40，50入隊(duì)01234=maxSize-1fr50(c)元素20，30，40依次出隊(duì)01234=maxSize-1fr50(d)元素60入隊(duì)01234=maxSize-1fr603.2隊(duì)列3.2.2隊(duì)列的順序表示

2.循環(huán)隊(duì)列表示法

把數(shù)組從邏輯上看成是一個(gè)頭尾相連的環(huán)。（a）空隊(duì)列滿隊(duì)列front==rear實(shí)際仍有一個(gè)元素的空間未使用0fr12340f123420304050r3.2隊(duì)列3.2.2隊(duì)列的順序表示

2.循環(huán)隊(duì)列表示法注意r值的變化：

4+1=>00f123420304050r（b）元素20，30，40，50入隊(duì)列（c）元素20，30，40出隊(duì)列0f123450r（d）元素60，70入隊(duì)列0f123450r60703.2隊(duì)列3.2.2隊(duì)列的順序表示

2.循環(huán)隊(duì)列表示法

實(shí)現(xiàn)循環(huán)隊(duì)列操作：

(1)為使入隊(duì)和出隊(duì)實(shí)現(xiàn)循環(huán)，可以利用取余運(yùn)算符%。

(2)隊(duì)頭指針進(jìn)一：

front=(front+1)%maxSize；

(3)隊(duì)尾指針進(jìn)一：

rear=(rear+1)%maxSize；

(4)空隊(duì)列：當(dāng)front==rear時(shí)為空隊(duì)列，

(5)滿隊(duì)列：當(dāng)(rear+1)%maxSize==front時(shí)為滿隊(duì)列。滿隊(duì)列時(shí)實(shí)際仍有一個(gè)元素的空間未使用。3.2隊(duì)列3.2.2隊(duì)列的順序表示

3.順序隊(duì)列類template<classT>classSeqQueue:publicQueue<T>{public:SeqQueue(intmSize);~SeqQueue(){delete[]q;}

boolIsEmpty()const；

boolIsFull()const；

boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear(){front=rear=0;}private:intfront,rear;intmaxSize;T*q;};0fr12343.2隊(duì)列3.2.2隊(duì)列的順序表示

4.動(dòng)態(tài)一維數(shù)組描述順序隊(duì)列類template<classT>classSeqQueue:publicQueue<T>{public:……

private:intfront,rear;intmaxSize;T*q;}01…n-1…maxSize-1frontrearq……3.2隊(duì)列3.2.2隊(duì)列的順序表示

4.動(dòng)態(tài)一維數(shù)組描述順序隊(duì)列類01…n-1…maxSize-1frontrearq……構(gòu)造函數(shù)template<classT>SeqQueue<T>::SeqQueue(intmSize){//生成一個(gè)空隊(duì)列

maxSize=mSize;q=newT[maxSize];front=rear=0;}析構(gòu)函數(shù)~SeqQueue(){delete[]q;}3.2隊(duì)列3.2.2隊(duì)列的順序表示

5.在順序存儲(chǔ)表示下實(shí)現(xiàn)隊(duì)列定義的操作template<classT>boolSeqQueue<T>::IsEmpty()const{returnfront==rear;}template<classT>boolSeqQueue<T>::IsFull()const{return(rear+1)%maxSize==front;}（1）判空（2）判滿3.2隊(duì)列3.2.2隊(duì)列的順序表示

5.在順序存儲(chǔ)表示下實(shí)現(xiàn)隊(duì)列定義的操作template<classT>boolSeqQueue<T>::Front(T&x){if(IsEmpty()){cout<<"empty"<<endl;returnfalse;}x=q[(front+1)%maxSize];returntrue;}（3）取隊(duì)列元素0f123420304050r3.2隊(duì)列3.2.2隊(duì)列的順序表示

5.在順序存儲(chǔ)表示下實(shí)現(xiàn)隊(duì)列定義的操作template<classT>boolSeqQueue<T>::EnQueue(Tx){if(IsFull()){cout<<"Full"<<endl;returnfalse;}q[(rear=(rear+1)%maxSize)]=x;returntrue;}（4）進(jìn)隊(duì)列（插入）0f123420304050r元素50入隊(duì)列0f1234203040r3.2隊(duì)列3.2.2隊(duì)列的順序表示

5.在順序存儲(chǔ)表示下實(shí)現(xiàn)隊(duì)列定義的操作template<classT>boolSeqQueue<T>::DeQueue(){if(IsEmpty()){cout<<"Underflow"<<endl;returnfalse;}front=(front+1)%maxSize;returntrue;}（5）出隊(duì)列（刪除）0f123420304050r0f123450r

元素20，30，40出隊(duì)列3.2隊(duì)列3.2.3隊(duì)列的鏈接表示隊(duì)列的鏈接表示法（鏈?zhǔn)疥?duì)列）鏈?zhǔn)疥?duì)列的定義和操作的實(shí)現(xiàn)類似于單鏈表。課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列

3.2.1隊(duì)列抽象數(shù)據(jù)類型

3.2.2隊(duì)列的順序表示

3.2.3隊(duì)列的鏈接表示3.3表達(dá)式的計(jì)算3.4遞歸不帶表頭結(jié)點(diǎn)的單鏈表a0an-1…front∧圖3-3鏈?zhǔn)疥?duì)列

a1a2rear3.2隊(duì)列3.2.3隊(duì)列的鏈接表示隊(duì)列的鏈接表示法（鏈?zhǔn)疥?duì)列）a0an-1…front∧圖3-3鏈?zhǔn)疥?duì)列

a1a2rear入隊(duì)列EnQueue(Tx)Node<T>*q=newNode<T>;q->element=x;q->link=NULL;rear->link=q;rear=q;出隊(duì)列DeQueue()Node<T>*q=front;front=front->link;delq;3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.1表達(dá)式課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列3.3表達(dá)式的計(jì)算

3.3.1表達(dá)式

3.3.2后綴表達(dá)式求值

3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式3.4遞歸

表達(dá)式：表達(dá)式習(xí)慣的書(shū)寫(xiě)形式是一個(gè)雙目運(yùn)算符位于兩個(gè)操作數(shù)之間，如a＋b;還有單目運(yùn)算符，如I++和-a。條件運(yùn)算符是C/C++語(yǔ)言中惟一的三目運(yùn)算符。

中綴表達(dá)式：操作符在兩個(gè)操作數(shù)之間的表達(dá)式,如：a/(b-c)+d*e

前綴表達(dá)式：操作符放在兩個(gè)操作數(shù)之前的表達(dá)式,如：+/a-bc*de

后綴表達(dá)式：操作符放在兩個(gè)操作數(shù)之后的表達(dá)式（逆波蘭表達(dá)式）如：abc-/de*+3.3堆棧的應(yīng)用—表達(dá)式計(jì)算逆波蘭式（ReversePolishnotation，RPN）

J.Lukasiewicz

19293.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.1表達(dá)式表3-1C++中部分操作符的優(yōu)先級(jí)操作符優(yōu)先級(jí)-,!7*,/,%6+,-5<,<=,>,>=4==,!=3&&2||1

有括號(hào)時(shí)先計(jì)算括號(hào)號(hào)中的表達(dá)式；高優(yōu)先級(jí)先計(jì)算同級(jí)操作符計(jì)算：從左到右，或從右到左3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值比較中綴表達(dá)式及其對(duì)應(yīng)的后綴表達(dá)式的例子表3.2中綴表達(dá)式和后綴表達(dá)式中綴表達(dá)式后綴表達(dá)式a*b+cab*c+a*b/cab*c/a*b*c*d*e*fab*c*d*e*f*a+(b*c+d)/eabc*d+e/+a*((b+c)/(d-e)-f)abc+de-/f-*a/(b-c)+d*eabc-/de*+課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列3.3表達(dá)式的計(jì)算

3.3.1表達(dá)式

3.3.2后綴表達(dá)式求值

3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式3.4遞歸3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值后綴表達(dá)式求值優(yōu)點(diǎn)：1）無(wú)界限符；2）求值時(shí)無(wú)需考慮操作符的優(yōu)先級(jí)。因此用后綴表達(dá)式求值計(jì)算簡(jiǎn)便，在編譯程序中常用。利用棧很容易計(jì)算后綴表達(dá)式的值。為了方便算法的實(shí)現(xiàn)，在后綴表達(dá)式的后面，通常會(huì)加上1個(gè)后綴表達(dá)式的結(jié)束符“＃”。3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值后綴表達(dá)式求值算法:

（1）從左往右順序掃描后綴表達(dá)式；（2）遇到操作數(shù)就進(jìn)棧；（3）遇到操作符就從棧中彈出兩個(gè)操作數(shù)，執(zhí)行該操作符規(guī)定的運(yùn)算；并將結(jié)果進(jìn)棧；（4）重復(fù)上述操作，直到表達(dá)式結(jié)束。彈出棧頂元素即為結(jié)果。

3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值642-/32*+#棧操作遇到結(jié)束符，彈出棧頂元素9即為結(jié)果#96、3出棧，計(jì)算3+6，結(jié)果9進(jìn)棧+632、3出棧，計(jì)算3*2，結(jié)果6進(jìn)棧*2332進(jìn)棧2333進(jìn)棧332、6出棧，計(jì)算6/2，結(jié)果3進(jìn)棧/262、4出棧，計(jì)算4-2，結(jié)果2進(jìn)棧-2462進(jìn)棧264

6掃描項(xiàng)表3.3后綴表達(dá)式的計(jì)算6進(jìn)棧64進(jìn)棧43.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值642-/32*+#6-24/32*+#642=22利用棧計(jì)算后綴表達(dá)式值的演示3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值利用棧計(jì)算后綴表達(dá)式值的演示233642-/32*+#6-24/32*+#=3263.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值利用棧計(jì)算后綴表達(dá)式值的演示33642-/32*+#6-24/32*+#=2663.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值利用棧計(jì)算后綴表達(dá)式值的演示63=642-/32*+#6-24/32*+#9=9==>6/(4-2)+3*26

4

2

-

/

3

2

*

+=93.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值在Linux系統(tǒng)中有后綴表達(dá)式計(jì)算器。$>dc43+p73.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值舉例：模擬一個(gè)簡(jiǎn)單的計(jì)算器假設(shè)該計(jì)算器可以接收后綴表達(dá)式，但只進(jìn)行+、-、*、/和^運(yùn)算。為實(shí)現(xiàn)計(jì)算器，定義一個(gè)計(jì)算器類。程序3.5計(jì)算器類#include”SeqStack.h”#include<math.h>classCalculator{public:Calculator(intmaxSize):s(maxSize){};//構(gòu)造函數(shù)

voidRun();voidClear(s.Clear();)private:SeqStack<double>s;//私有數(shù)據(jù)成員是一個(gè)棧，用于存放操作數(shù)

voidPushOperand(double);//操作數(shù)進(jìn)棧

boolGetOperands(double&,double&);//兩個(gè)操作數(shù)出棧

voidDoOperator(char);//操作符進(jìn)行處理（遇到操作符時(shí)調(diào)用）};3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值舉例：模擬一個(gè)簡(jiǎn)單的計(jì)算器成員函數(shù)的實(shí)現(xiàn)：voidCalculator::PushOperand(doubleop){s.Push(op);//操作數(shù)進(jìn)棧}BOOLCalculator::GetOperands(double&op1,double&op2){//兩個(gè)操作數(shù)出棧

if(!s.Top(op1)){ cerr<<"Missingoperand!"<<endl;returnfalse;}s.Pop();if(!s.Top(op2)){ cerr<<"Missingoperand!"<<endl;returnfalse;}s.Pop();returntrue;}3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值舉例：模擬一個(gè)簡(jiǎn)單的計(jì)算器voidCalculator::DoOperator(charoper)//遇到操作符時(shí)調(diào)用{boolresult;doubleoper1,oper2;result=GetOperands(oper1,oper2);//從棧中彈出2個(gè)操作數(shù)3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值舉例：模擬一個(gè)簡(jiǎn)單的計(jì)算器if(result)//執(zhí)行操作符oper指定的運(yùn)算

switch(oper)//根據(jù)操作符做相應(yīng)的運(yùn)算，先出棧的操作數(shù)oper1{//放在操作符的右邊，后出棧的oper2放在左邊

case'+':s.Push(oper2+oper1);break;case'-':s.Push(oper2-oper1);break;case'*':s.Push(oper2*oper1);break;case'/':if(fabs(oper1)<1e-6){//如果分母為0，則做出錯(cuò)處理

cerr<<"Divideby0!"<<endl; Clear();} elses.Push(oper2/oper1);break;case'^':s.Push(pow(oper2,oper1));break;}elseClear();}3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值舉例：模擬一個(gè)簡(jiǎn)單的計(jì)算器voidCalculator::Run(){charc;doublenewop;while(cin>>c,c!='#'){//從輸入流試讀入一個(gè)字符，遇結(jié)束符結(jié)束

switch(c){//讀入的字符做如下處理

case'+':case'-':case'*':case'/':case'^':DoOperator(c);break;//是操作符則進(jìn)行相應(yīng)的計(jì)算

default:cin.putback(c);//如不是操作符，則將試讀入的字符放回輸入流

cin>>newop;//讀入一個(gè)操作數(shù)

PushOperand(newop);break;//操作數(shù)進(jìn)棧

}}if(s.Top(newop))cout<<newop<<endl;//取棧頂元素，得結(jié)果輸出}3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.2后綴表達(dá)式求值舉例：模擬一個(gè)簡(jiǎn)單的計(jì)算器計(jì)算器類的應(yīng)用程序：#include“calculator.h”constintSIZE=20;voidmain(){CalculatorCal(SIZE);Cal.Run();}輸入：642-/32*+#結(jié)果：93.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式注意：只考慮左結(jié)合的雙目運(yùn)算。每個(gè)表達(dá)式以“?！碧?hào)作為其結(jié)束標(biāo)記。輸入中綴表達(dá)式由運(yùn)算符、操作數(shù)、園括弧和‘＃’四種不同類型的項(xiàng)組成的序列輸出后綴表達(dá)式課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列3.3表達(dá)式的計(jì)算

3.3.1表達(dá)式

3.3.2后綴表達(dá)式求值

3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式3.4遞歸3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式棧內(nèi)優(yōu)先級(jí)isp(in-stackpriority)棧外優(yōu)先級(jí)icp(incomingpriority)對(duì)未進(jìn)棧的左括號(hào)賦以最高優(yōu)先級(jí)，對(duì)已進(jìn)棧的左括號(hào)賦以最低優(yōu)先級(jí)。假定表達(dá)式的語(yǔ)法正確性檢查已在表達(dá)式轉(zhuǎn)換之前完成。3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式轉(zhuǎn)換步驟：（1）從左到右掃描中綴表達(dá)式，遇到#轉(zhuǎn)（6）；否則繼續(xù)；（2）遇到操作數(shù)直接輸出；（不進(jìn)棧）（3）遇到“）”，則連續(xù)出棧輸出，直到遇到“（”為止（注意：“（”出棧但不輸出）；（4）若是其它操作符，則與棧頂?shù)牟僮鞣容^優(yōu)先級(jí)；若小于棧頂操作符的棧內(nèi)優(yōu)先級(jí)，則連續(xù)出棧輸出，直到大于等于棧頂操作符的棧內(nèi)優(yōu)先級(jí)結(jié)束，該操作符進(jìn)棧；（5）轉(zhuǎn)（1）繼續(xù)；（6）輸出棧中剩余操作符（#除外）。3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式a(/中綴表達(dá)式:a/(b-c)+d*e后綴表達(dá)式:abc-/de*+bc-)d+*e#3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式中綴表達(dá)式:a/(b-c)+d*e后綴表達(dá)式:abc-/de*+a(/bc-d+*e#3.3堆棧的應(yīng)用—表達(dá)式計(jì)算3.3.3中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式中綴表達(dá)式:a/(b-c