第3章棧和隊列

第3章棧和隊列

3.1棧棧的邏輯結(jié)構(gòu)（a1,a2,……,an）棧：限定僅在表的一端進行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。不含任何數(shù)據(jù)元素的棧。

棧頂棧底a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂

3.1棧棧的邏輯結(jié)構(gòu)棧的操作特性：后進先出a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂

3.1棧棧的邏輯結(jié)構(gòu)例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：棧的邏輯結(jié)構(gòu)

3.1棧棧底棧頂ab棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況1：

3.1棧棧底棧頂ab棧頂出棧序列：b情況2：例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)

3.1棧棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況2：

3.1棧出棧序列：b、a、c注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況3：

3.1棧出棧序列：a、b、c情況4：出棧序列：a、c、b情況5：棧的抽象數(shù)據(jù)類型定義ADTStackData

棧中元素具有相同類型及后進先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系OperationInitStack

前置條件：棧不存在輸入：無功能：棧的初始化輸出：無后置條件：構(gòu)造一個空棧

3.1棧DestroyStack

前置條件：棧已存在輸入：無功能：銷毀棧輸出：無后置條件：釋放棧所占用的存儲空間Push

前置條件：棧已存在輸入：元素值x

功能：在棧頂插入一個元素x

輸出：如果插入不成功，拋出異常后置條件：如果插入成功，棧頂增加了一個元素棧的抽象數(shù)據(jù)類型定義

3.1棧Pop

前置條件：棧已存在輸入：無功能：刪除棧頂元素輸出：如果刪除成功，返回被刪元素值，否則，拋出異常后置條件：如果刪除成功，棧減少了一個元素GetTop

前置條件：棧已存在輸入：無功能：讀取當前的棧頂元素輸出：若棧不空，返回當前的棧頂元素值后置條件：棧不變棧的抽象數(shù)據(jù)類型定義

3.1棧Empty

前置條件：棧已存在輸入：無功能：判斷棧是否為空輸出：如果棧為空，返回1，否則，返回0

后置條件：棧不變endADT棧的抽象數(shù)據(jù)類型定義

3.1棧棧的順序存儲結(jié)構(gòu)及實現(xiàn)順序?！獥５捻樞虼鎯Y(jié)構(gòu)如何改造數(shù)組實現(xiàn)棧的順序存儲？

012345678a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top

3.1棧出棧：top減1進棧：top加1?？眨簍op=-1

012345678a1topa2topa3top棧滿：top=MAX_SIZE-1棧的順序存儲結(jié)構(gòu)及實現(xiàn)

3.1棧順序棧類的聲明constintStackSize=100;template<classDataType>classseqStack{public:seqStack();~seqStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();boolEmpty();private:DataTypedata[StackSize];inttop;}

3.1棧順序棧的實現(xiàn)——入棧template<classDataType>voidseqStack<DataType>::Push(DataTypex){if(top==StackSize-1)throw“溢出”;

top++;data[top]=x;}操作接口：voidPush(DataTypex);時間復(fù)雜度？data[++top]=x

3.1棧順序棧的實現(xiàn)——出棧template<classDataType>DataTypeseqStack<DataType>::Pop(){if(top==-1)throw“溢出”;

x=data[top--];

returnx;}操作接口：DataTypePop();時間復(fù)雜度？

3.1棧兩棧共享空間解決方案1：直接解決：為每個棧開辟一個數(shù)組空間。解決方案2：

順序棧單向延伸——使用一個數(shù)組來存儲兩個棧在一個程序中需要同時使用具有相同數(shù)據(jù)類型的兩個棧，如何順序存儲這兩個棧？會出現(xiàn)什么問題？如何解決？

3.1棧兩棧共享空間：使用一個數(shù)組來存儲兩個棧，讓一個棧的棧底為該數(shù)組的始端，另一個棧的棧底為該數(shù)組的末端，兩個棧從各自的端點向中間延伸。兩棧共享空間

3.1棧棧1的底固定在下標為0的一端；棧2的底固定在下標為StackSize-1的一端。

top1和top2分別為棧1和棧2的棧頂指針；Stack_Size為整個數(shù)組空間的大?。▓D中用S表示）；a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1棧1底棧2底

3.1棧top1=-1什么時候棧1為空？a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1top1

3.1棧top1=-1什么時候棧1為空？a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1什么時候棧2為空？top2top2=Stack_Size

3.1棧top1=-1什么時候棧1為空？a1

a2……aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1什么時候棧2為空？top2=Stack_Size什么時候棧滿？top2=top1+1

3.1棧constintStackSize=100;template<classDataType>classBothStack{public:BothStack();~BothStack();voidPush(inti,DataTypex);DataTypePop(inti);

DataTypeGetTop(inti);

boolEmpty(inti);private:DataTypedata[StackSize];

inttop1,top2;};兩棧共享空間類的聲明

3.1棧1.如果棧滿，則拋出上溢異常；2.判斷是插在棧1還是棧2；2.1若在棧1插入，則2.1.1top1加1;

2.1.2在top1處填入x；2.2若在棧2插入，則2.2.1top2減1;

2.2.2在top2處填入x；兩棧共享空間的實現(xiàn)——插入操作接口：voidPush(inti,DataTypex);

3.1棧1.若是在棧1刪除，則

1.1若棧1為空棧，拋出下溢異常；

1.2刪除并返回棧1的棧頂元素；2.若是在棧2刪除，則

2.1若棧2為空棧，拋出下溢異常；

2.2刪除并返回棧2的棧頂元素；兩棧共享空間的實現(xiàn)——刪除操作接口：DataTypePop(inti);

3.1棧棧的鏈接存儲結(jié)構(gòu)及實現(xiàn)鏈棧：棧的鏈接存儲結(jié)構(gòu)firsta1a2an∧ai鏈棧需要加頭結(jié)點嗎？如何改造鏈表實現(xiàn)棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點。

3.1棧棧的鏈接存儲結(jié)構(gòu)及實現(xiàn)棧頂棧底鏈棧：棧的鏈接存儲結(jié)構(gòu)topanan-1a1∧firsta1a2an∧ai兩種示意圖在內(nèi)存中對應(yīng)同一種狀態(tài)，啟示？topa1an-1an∧棧頂棧底

3.1棧鏈棧的類聲明template<classDataType>classLinkStack{

public:LinkStack();

~LinkStack();

voidPush(DataTypex);DataTypePop();DataTypeGetTop();boolEmpty();private:Node<DataType>*top;}

3.1棧template<classDataType>voidLinkStack<DataType>

::Push(DataTypex){s=newNode<DataType>;s->data=x;s->next=top;top=s;}topanan-1a1∧鏈棧的實現(xiàn)——插入xstop操作接口：voidPush(DataTypex);

為什么沒有判斷棧滿？

3.1棧template<classDataType>DataTypeLinkStack<DataType>::Pop(){if(top==NULL)

throw"下溢";

x=top->data;p=top;top=top->next;

deletep;returnx;}鏈棧的實現(xiàn)——刪除操作接口：DataTypePop();

topanan-1a1∧topp

top++可以嗎？

3.1棧順序棧和鏈棧的比較時間性能：相同，都是常數(shù)時間O(1)?？臻g性能：順序棧：有元素個數(shù)的限制和空間浪費的問題。鏈棧：沒有棧滿的問題，只有當內(nèi)存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。

總之，當棧的使用過程中元素個數(shù)變化較大時，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。

3.1棧棧的應(yīng)用舉例—數(shù)制轉(zhuǎn)換十進制轉(zhuǎn)其它進制（2，8，16）十進制整數(shù)轉(zhuǎn)換成其它進制的整數(shù)采用的方法是：

除n取余，逆排如：(23)10=(10111)2231121251221210201 SeqStack<int>stack; inta=23,b=2; while(a!=0){ stack.Push(a%b); a=a/b; } while(stack.IsEmpty()==0){ cout<<stack.Pop(); } cout<<endl;3.2隊列隊列的邏輯結(jié)構(gòu)隊列：只允許在一端進行插入操作，而另一端進行刪除操作的線性表。允許插入（也稱入隊、進隊）的一端稱為隊尾，允許刪除（也稱出隊）的一端稱為隊頭。空隊列：不含任何數(shù)據(jù)元素的隊列。（a1,a2,……,an）隊尾隊頭隊列的操作特性：先進先出a1a2a3入隊隊尾隊頭出隊隊頭隊列的邏輯結(jié)構(gòu)3.2隊列隊列的抽象數(shù)據(jù)類型定義ADTQueueData

隊列中元素具有相同類型及先進先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系OperationInitQueue

前置條件：隊列不存在輸入：無功能：初始化隊列輸出：無后置條件：創(chuàng)建一個空隊列3.2隊列

DestroyQueue

前置條件：隊列已存在輸入：無功能：銷毀隊列輸出：無后置條件：釋放隊列所占用的存儲空間

EnQueue

前置條件：隊列已存在輸入：元素值x

功能：在隊尾插入一個元素輸出：如果插入不成功，拋出異常后置條件：如果插入成功，隊尾增加了一個元素隊列的抽象數(shù)據(jù)類型定義3.2隊列

DeQueue

前置條件：隊列已存在輸入：無功能：刪除隊頭元素輸出：如果刪除成功，返回被刪元素值后置條件：如果刪除成功，隊頭減少了一個元素

GetQueue

前置條件：隊列已存在輸入：無功能：讀取隊頭元素輸出：若隊列不空，返回隊頭元素后置條件：隊列不變隊列的抽象數(shù)據(jù)類型定義3.2隊列Empty

前置條件：隊列已存在輸入：無功能：判斷隊列是否為空輸出：如果隊列為空，返回1，否則，返回0

后置條件：隊列不變endADT隊列的抽象數(shù)據(jù)類型定義3.2隊列01234入隊出隊隊列的順序存儲結(jié)構(gòu)及實現(xiàn)順序隊列——隊列的順序存儲結(jié)構(gòu)如何改造數(shù)組實現(xiàn)隊列的順序存儲？例：a1a2a3a4依次入隊a1a2a3a4rearrearrearrear入隊操作時間性能為O(1)3.2隊列如何改造數(shù)組實現(xiàn)隊列的順序存儲？例：a1a2依次出隊隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a1a2a3a4rear3.2隊列如何改造數(shù)組實現(xiàn)隊列的順序存儲？例：a1a2依次出隊隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a2a3a4rear3.2隊列如何改造數(shù)組實現(xiàn)隊列的順序存儲？例：a1a2依次出隊隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a3a4rear出隊操作時間性能為O(n)3.2隊列隊列的順序存儲結(jié)構(gòu)及實現(xiàn)如何改進出隊的時間性能？放寬隊列的所有元素必須存儲在數(shù)組的前n個單元這一條件，只要求隊列的元素存儲在數(shù)組中連續(xù)的位置。設(shè)置隊頭、隊尾兩個指針

3.2隊列隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊例：a1a2a3a4依次入隊a1a2a3a4rearrearrearrear入隊操作時間性能仍為O(1)frontrear3.2隊列約定：隊頭指針front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素。例：a1a2依次出隊隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a1a2a3a4rearfrontfrontfront出隊操作時間性能提高為O(1)3.2隊列例：a1a2依次出隊隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a3a4rearfront隊列的移動有什么特點？3.2隊列例：a1a2依次出隊隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a3a4rearfront整個隊列向數(shù)組下標較大方向移動單向移動性3.2隊列假溢出：當元素被插入到數(shù)組中下標最大的位置上之后，隊列的空間就用盡了，盡管此時數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。隊列的順序存儲結(jié)構(gòu)及實現(xiàn)繼續(xù)入隊會出現(xiàn)什么情況？01234入隊出隊a3a4rearfronta5rear3.2隊列循環(huán)隊列：將存儲隊列的數(shù)組頭尾相接。隊列的順序存儲結(jié)構(gòu)及實現(xiàn)如何解決假溢出？01234入隊出隊a3a4fronta5rearreara63.2隊列不存在物理的循環(huán)結(jié)構(gòu)，用軟件方法實現(xiàn)。隊列的順序存儲結(jié)構(gòu)及實現(xiàn)如何實現(xiàn)循環(huán)隊列？01234入隊出隊a3a4frontreara63.2隊列取余（求模）：(4＋1)%5＝0如何判斷循環(huán)隊列隊空？隊空的臨界狀態(tài)隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a3rearfront3.2隊列如何判斷循環(huán)隊列隊空？執(zhí)行出隊操作隊空：front=rear隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a3frontrearfront3.2隊列如何判斷循環(huán)隊列隊滿？隊滿的臨界狀態(tài)隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a3a4fronta5reara63.2隊列如何判斷循環(huán)隊列隊滿？執(zhí)行入隊操作隊滿：front=rear隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊出隊a3a4fronta5reara6reara73.2隊列方法一：附設(shè)一個存儲隊列中元素個數(shù)的變量num，當num=0時隊空，當num=QueueSize時為隊滿；方法二：設(shè)置標志flag，當front=rear且flag=0時為隊空，當front=rear且flag=1時為隊滿；方法三：修改隊滿條件，浪費一個元素空間，即隊滿時數(shù)組中還有一個空閑單元。如何確定不同的隊空、隊滿的判定條件？為什么要將隊空和隊滿的判定條件分開？隊列的順序存儲結(jié)構(gòu)及實現(xiàn)3.2隊列隊滿的條件：(rear+1)modQueueSize=front隊列的順序存儲結(jié)構(gòu)及實現(xiàn)01234入隊rear<fronta3a4fronta5reara6出隊01234入隊rear>fronta3a4fronta5reara6出隊3.2隊列循環(huán)隊列類的聲明constintQueueSize=100;template<classDataType>classCirQueue{public:CirQueue()；~CirQueue()；

voidEnQueue(DataTypex);DataTypeDeQueue();

DataTypeGetQueue();

boolEmpty()；private:DataTypedata[QueueSize];

intfront,rear;};3.2隊列template<classDataType>voidCirQueue<DataType>::EnQueue(DataTypex){if((rear+1)%QueueSize==front)throw"上溢";

rear=(rear+1)%QueueSize;

data[rear]=x;}循環(huán)隊列的實現(xiàn)——入隊01234入隊出隊a3a4rearfronta5rear3.2隊列01234入隊a4a5a6出隊template<classDataType>DataTypeCirQueue<DataType>

::DeQueue(){if(rear==front)throw"下溢";

front=(front+1)%QueueSize;returndata[front];}循環(huán)隊列的實現(xiàn)——出隊frontrearfronta33.2隊列template<classDataType>DataTypeCirQueue<DataType>

::GetQueue(){if(rear==front)throw"下溢";

i=(front+1)%QueueSize;

returndata[i];}循環(huán)隊列的實現(xiàn)——讀隊頭元素01234入隊a4a5a6出隊frontreara3i3.2隊列隊列的鏈接存儲結(jié)構(gòu)及實現(xiàn)鏈隊列：隊列的鏈接存儲結(jié)構(gòu)隊頭指針即為鏈表的頭指針firsta1a2an∧如何改造單鏈表實現(xiàn)隊列的鏈接存儲？rearfront3.2隊列隊列的鏈接存儲結(jié)構(gòu)及實現(xiàn)非空鏈隊列fronta1a2an∧rear空鏈隊列front∧rear3.2隊列鏈隊列類的聲明template<classDataType>classLinkQueue{public:LinkQueue();~LinkQueue();voidEnQueue(DataTypex);DataTypeDeQueue();

DataTypeGetQueue()；boolEmpty()；private:Node<DataType>*front,*rear;};3.2隊列操作接口：LinkQueue();

算法描述：template<classDataType>LinkQueue<DataType>

::LinkQueue(){front=newNode<DataType>;front->next=NULL;rear=front;}鏈隊列的實現(xiàn)——構(gòu)造函數(shù)front∧rear3.2隊列xs鏈隊列的實現(xiàn)——入隊操作接口：voidEnQueue(DataTypex);fronta1an∧rear∧rearfrontxs∧∧rearrear算法描述：s->next=NULL;rear->next=s;rear=s;如何沒有頭結(jié)點會怎樣？3.2隊列xs鏈隊列的實現(xiàn)——入隊操作接口：voidEnQueue(DataTypex);fronta2an∧rear∧rear算法描述：s->next=NULL;rear->next=s;rear=s;如何沒有頭結(jié)點會怎樣？a13.2隊列鏈隊列的實現(xiàn)——入隊操作接口：voidEnQueue(DataTypex);front=rear=NULLxs∧rear算法描述：s->next=NULL;rear=s;front=s;如何沒有頭結(jié)點會怎樣？front算法描述：s->next=NULL;rear->next=s;rear=s;3.2隊列鏈隊列的實現(xiàn)——入隊template<classDataType>voidLinkQueue<DataType>

::EnQueue(DataTypex){s=newNode<DataType>;s->data=x;s->next=NULL;rear->next=s;rear=s;}3.2隊列鏈隊列的實現(xiàn)——出隊fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;3.2隊列鏈隊列的實現(xiàn)——出隊fronta1a2an∧rearp考慮邊界情況：隊列中只有一個元素？fronta1p∧rear∧rear算法描述：if(p->next==NULL)rear=front;如何判斷邊界情況？3.2隊列template<classDataType>DataTypeLinkQueue<DataType>

::DeQueue(){if(rear==front)throw"下溢";p=front->next;x=p->data;front->next=p->next;if(p->next==NULL)rear=front;deletep;returnx;}鏈隊列的實現(xiàn)——出隊3.2隊列循環(huán)隊列和鏈隊列的比較時間性能:循環(huán)隊列和鏈隊列的基本操作都需要常數(shù)時間O(1)。空間性能:循環(huán)隊列：必須預(yù)先確定一個固定的長度，所以有存儲元素個數(shù)的限制和空間浪費的問題。鏈隊列：沒有隊列滿的問題，只有當內(nèi)存沒有可用空間時才會出現(xiàn)隊列滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。3.2隊列本章總結(jié)特殊線性表棧隊列⑴棧的定義⑵操作特性⑶ADT定義⑴隊列定義⑵操作特性⑶ADT定義順序棧鏈棧循環(huán)隊列鏈隊列邏輯結(jié)構(gòu)存儲結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)比較比較比較⑴基本操作的實現(xiàn)⑵時間性能⑴基本操作的實現(xiàn)⑵時間性能棧的應(yīng)用：表達式求解一個表達式由操作數(shù)（亦稱運算對象）、操作符（亦稱運算符）和分界符組成。算術(shù)表達式有三種表示：中綴(infix)表示

<操作數(shù)><操作符><操作數(shù)>，如A+B；前綴(prefix)表示

<操作符><操作數(shù)><操作數(shù)>，如+AB；后綴(postfix)表示

<操作數(shù)><操作數(shù)><操作符>，如AB+；中綴表達式

a*b+(c–d/e)*f后綴表達式ab*

cde/-f*+前綴表達式 +*ab

*-c/def表達式事例結(jié)論：1）操作數(shù)之間的相對次序不變；2）運算符的相對次序不同；3）后綴表達式的運算規(guī)則為：

運算符在式中出現(xiàn)的順序恰為表達式的運算順序；

每個運算符和在它們之前且緊靠它的兩個操作數(shù)構(gòu)成一個最小的表達式4）前綴表達式的運算規(guī)則為：連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一個最小的表達式1.后綴表達式（逆波蘭式）求值從左向右順序地掃描表達式，并用一個棧暫存掃描到的操作數(shù)或計算結(jié)果。在后綴表達式的計算順序中已隱含了加括號的優(yōu)先次序，括號在后綴表達式中不出現(xiàn)。計算例ab*

cde/-f*+t1t3t4t2t5后綴表達式用什么來存儲?字符棧、字符數(shù)組、字符串其實這三者本質(zhì)上都是一樣的，都可以實現(xiàn)ab*cde/-f*+T1=T2=T3=T4=T5=T1T2T3T4操作數(shù)或中間結(jié)果棧ST5

1.初始化棧S；

2.從左到右依次掃描表達式的每個字符，執(zhí)行下述操作；2.1若當前字符是運算對象，則入棧S，處理下個字符

2.2若當前字符是運算符，則從棧S出棧兩個運算對象，執(zhí)行運算并將結(jié)果入棧S，處理下一個字符；

3.輸出棧S的棧頂元素，即表達式的運算結(jié)果；算法描述——偽代碼double

calculate(char

postfix[]){

SeqStack<double>

S;

int

i

=

0,x

=

0;

char

ch

=

postfix[i];

double

a,b,result;

while(ch

!=

'\0'){

if(ch

>=

'0'

&&

ch

<=

'9'){

x

=

ch

-

'0';

S.Push(x);

ch

=

postfix[++i];

}

//

if

else{

b

=

S.Pop();

a

=

S.Pop();

if(ch

==

'+')

result

=

a

+

b;

if(ch

==

'-')

result

=

a

-

b;

if(ch

==

'*')

result

=

a

*

b;

if(ch

==

'/')

result

=

a

/

b;

S.Push(result);

ch

=

postfix[++i];

}

return

S.GetTop();

}

如果參與計算的數(shù)不是一位怎么處理？之前入棧的是每個數(shù)組元素，現(xiàn)在要把幾個數(shù)組元素組合在一起再入棧，所以表達式中的數(shù)要有分隔符，能夠把每個數(shù)區(qū)分開來charpostfix[]="121153-2*4-+";double

calculate(char

postfix[]){

SeqStack<double>

S;

int

i

=

0,

x

=

0;

char

ch

=

postfix[i];

double

a,b,result;

while(ch

!=

'\0'){

if(ch

>=

'0'

&&

ch

<=

'9'){

x

=

0;

while(ch

!=

'

'){

x

=

x

*

10

+

(ch

-

'0');

ch

=

postfixS[++i];

}//while

S.Push(x);

}

//if

else{

b

=

S.Pop();

a

=

S.Pop();

if(ch

==

'+')

result

=

a

+

b;

if(ch

==

'-')

result

=

a

-

b;

if(ch

==

'*')

result

=

a

*

b;

if(ch

==

'/')

result

=

a

/

b;

S.Push(result);

ch

=

postfix[++i];

}//else

//多位數(shù)時需要考慮ch為空格的情況

if(ch

==

'

'){

ch

=

postfix[++i];

}

}//while

return

S.GetTop();

}

2.中綴表達式轉(zhuǎn)后綴表達式中綴表達式

a*b+(c–d/e)*f后綴表達式ab*

cde/-f*+怎么轉(zhuǎn)換？優(yōu)先級高的先計算；優(yōu)先級相同的自左向右計算；當使用括號時從最內(nèi)層括號開始計算2.中綴表達式轉(zhuǎn)換為后綴表達式中綴表達式

a*b+(c–d/e)*f后綴表達式ab*

cde/-f*+分析：如：中綴表達式c-d/e，就計算機來講可以看成(c-d)/e，也可以看成c-(d/e),表達式的計算順序是從左到右，計算機也是從左向右遍歷，遍歷到“-”后，不是先計算，而是要看其后面的運算符，如果其是“+”或“-”先做“-”，如果是“/”那么要先做“/”，這樣的話就要把“-”先保存起來，就是棧的特點，所以可以用一個棧來保存運算符2.中綴表達式轉(zhuǎn)后綴表達式中綴表達式

a*b+(c–d/e)*f后綴表達式ab*

cde/-f*+規(guī)律：每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優(yōu)先級高的運算符領(lǐng)先于優(yōu)先級低的運算符ab*cde/-)*+運算符棧(f/0/0后綴表達式字符串中綴表達式字符串↑↑↑↑↑↑↑↑↑↑↑↑↑↑90各個算術(shù)操作符的優(yōu)先級isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對時。

1.初始化棧S,并將’\0’入棧；

2.從左到右依次掃描表達式的每個字符，執(zhí)行下述操作；2.1若當前字符是運算對象，則放入后綴表達式中，處理下個字符

2.2若當前字符是運算符

若其優(yōu)先級比棧S的棧頂運算符的優(yōu)先級高，則將該字符入棧S，處理下一個字符；

若其優(yōu)先級比棧S的棧頂運算符的優(yōu)先級低，則將棧頂元素彈出放入后綴表達式中； 2.2.3若其優(yōu)先級與棧S的棧頂運算符的優(yōu)先級相等，則將棧S棧頂元素彈出，處理下一個字符；

3.彈出棧S中的所有元素至后綴表達式中；算法描述——偽代碼char

*infixToPostfix(char

infix[]){

SeqStack<char>

S;

S.Push('\0');

int

i

=

0,

j

=

0;

char

ch

=

infix[i];

char

*postfix

=

new

char[100];

while(ch

!=

'\0'){

if(ch

>=

'0'

&&

ch

<=

'9'){

postfix[j++]

=

ch;

ch

=

infix[++i];

}//if

else{

if(icp(ch)

>

isp(S.GetTop())){

S.Push(ch);

ch

=

infix[++i];

}

else

if(icp(ch)

<

isp(S.GetTop())){

postfix[j++]

=

S.Pop();

}

else{

S.Pop();

ch

=

infix[++i];

}

}

}//while

while(S.IsEmpty()

==

0){//1表示空，0表示非空

postfix[j++]

=

S.Pop();

}

return

postfix;

}

intisp(charop){ switch(op){ case'\0': return0; break; case'(': return1; break; case'*': return5; break; case'/': return5; break; case'+': return3; break; case'-': return3; break; default: return6;}}inticp(charch){ switch(ch){ case'\0': return0; break; case'(': return6; break; case'*': return4; break; case'/': return4; break; case'+': return2; break; case'-': return2; break; default: return1; }}3.中綴表達式求值a*b+(c-d/e)*f中綴表達式求值，實際上是先將其轉(zhuǎn)換為后綴表達式，然后對后綴表達式求值，也就是將之前的兩個算法寫成一個需要使用兩個棧，操作符棧OPTR(operator)，操作數(shù)棧OPND(operand)t1t3t4t2t5ab*cde/-)*+(f/0運算符棧OPTR/0中綴表達式字符串操作數(shù)或中間結(jié)果棧OPND====T5=T1T2T3T4↑↑↑↑↑↑↑↑↑↑↑↑↑↑T1T2T3T4T5各個算術(shù)操作符的優(yōu)先級isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對時。將棧OPND和OPTR初始化為空，并將’\0’入棧OPTR；從左到右依次掃描中綴表達式的每個字符，放入ch中，執(zhí)行下述操作； 2.1若當前字符是運算對象，則入棧OPND，在中綴表達式中處理下個字符 2.2若當前字符是運算符且優(yōu)先級比棧OPTR的棧頂運算符的優(yōu)先級高，則入棧OPTR，在中綴表達式中處理下一個字符；算法描述——偽代碼 2.3若當前字符是運算符且優(yōu)先級比棧OPTR的棧頂運算符的優(yōu)先級低，則從棧OPND出棧兩個運算對象，從棧OPTR出棧一個運