數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)棧和隊(duì)列

數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)棧和隊(duì)列1

一、棧

1.棧的定義

棧(Stack)又稱堆棧，它是一種運(yùn)算受限的線性表，其限制是僅答應(yīng)在表的

一端進(jìn)行插入和刪除運(yùn)算。人們把此端稱為棧頂，棧頂?shù)牡谝粋€(gè)元素被稱為棧

頂元素，相對(duì)地，把另一端稱為棧底。向一個(gè)棧插入新元素又稱為進(jìn)?；蛉?/p>

棧，它是把該元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪

除元素又稱為出?；蛲藯?，它是把棧頂元素刪除掉，使其下面的相鄰元素成為

新的棧頂元素。

在日常生活中，有許多類似棧的例子，如刷洗盤子時(shí)，依次把每個(gè)洗凈的

盤子放到洗好的盤子上，相當(dāng)于進(jìn)棧；取用盤子時(shí)，從一摞盤子上一個(gè)接一個(gè)

地向下拿，相當(dāng)于出棧。又如向槍支彈夾里裝子彈時(shí)，子彈被一個(gè)接一個(gè)地壓

入，則為進(jìn)棧；射擊時(shí)子彈總是從頂部一個(gè)接一個(gè)地被射出，此為子彈出棧。

由于棧的插入和刪除運(yùn)算僅在棧頂一端進(jìn)行，后進(jìn)棧的元素必定先出棧，

所以又把棧稱為后進(jìn)先出表(LastInFirstOut,簡(jiǎn)稱LIFO)。

例如，假定一個(gè)棧S為(a,b,c),其中字符c的一端為棧頂，字符c為棧頂

元素。若向S壓入一個(gè)元素d,則S變?yōu)?a,b,c,d),此時(shí)字符d為棧頂元素；

若接著從棧S中依次刪除兩個(gè)元素，則首先刪除的是元素d,接著刪除的使元

素c,棧S變?yōu)?a,b),棧頂元素為b。

視頻教程'css.shtml'target』_blank'title=，div視頻教程'div2.棧的

存儲(chǔ)結(jié)構(gòu)

棧既然是一種線性表，所以線性表的順序存儲(chǔ)和鏈接存儲(chǔ)結(jié)構(gòu)同樣適用于

棧。

(1)棧的順序存儲(chǔ)結(jié)構(gòu)

棧的順序存儲(chǔ)結(jié)構(gòu)同樣需要使用一個(gè)數(shù)組和一個(gè)整型變量來(lái)實(shí)現(xiàn)，利用數(shù)

組來(lái)順序存儲(chǔ)棧中的所有元素，利用整型變量來(lái)存儲(chǔ)棧頂元素的下標(biāo)位置。假

定棧數(shù)組用stack[StackMaxSize]表示，指示棧頂位置的整型變量用top表

示，則元素類型為ElemType的棧的順序存儲(chǔ)類型可定義為：

ElemTypestack[StackMaxSize]；

inttop；

其中，StackMaxSize為一個(gè)整型全局常量，需事先通過(guò)const語(yǔ)句定義，

由它確定順序棧(即順序存儲(chǔ)的棧)的最大深度，又稱為長(zhǎng)度，即棧最多能夠存

儲(chǔ)的元素個(gè)數(shù)；由于top用來(lái)指示棧頂元素的位置，所以把它稱為棧頂指針。

棧的順序存儲(chǔ)結(jié)構(gòu)同樣可以定義在一個(gè)記錄類型中，假定該記錄類型用

Stack表示，則定義為：

structStack{

ElemTypestack[StackMaxSize]；

inttop；

);

在順序存儲(chǔ)的棧中，top的值為T表示?？眨看蜗驐Ｖ袎喝胍粋€(gè)元素

時(shí)，首先使top增1,用以指示新的棧頂位置，然后再把元素賦值到這個(gè)位置

上，每次從棧中彈出一個(gè)元素時(shí)，首先取出棧頂元素，然后使top減1,指示

前一個(gè)元素成為新的棧頂元素。由此可知，對(duì)順序棧的插入和刪除運(yùn)算相當(dāng)于

是在順序表(即順序存儲(chǔ)的線性表)的表尾進(jìn)行的，其時(shí)間復(fù)雜度為0(1)O

設(shè)一個(gè)棧S為(a,b,c,d,e),對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)如圖4T(a)所示。若向S

中插入一個(gè)元素f,則對(duì)應(yīng)如圖4T(b)所示。若接著執(zhí)行兩次出棧操作后，則

棧S對(duì)應(yīng)如圖4T(c)所示。若依次使棧S中的所有元素出棧，則s變?yōu)榭?，?/p>

圖4T(d)所示。在圖4T中棧是垂直畫出的，并且使下標(biāo)編號(hào)向上遞增，這樣

可以形象地表示出棧頂在上，棧底在下。

圖4-1棧的順序存儲(chǔ)結(jié)構(gòu)及操作過(guò)程

在一個(gè)順序棧中，若top已經(jīng)指向了StackMaxSizeT的位置，則表示棧

滿，若top的值已經(jīng)等于T,則表示?？?。向一個(gè)滿棧插入元素和從一個(gè)空棧

刪除元素都是不答應(yīng)的，應(yīng)該停止程序運(yùn)行或進(jìn)行非凡處理。

(2)棧的鏈接存儲(chǔ)結(jié)構(gòu)

棧的鏈接存儲(chǔ)結(jié)構(gòu)與線性表的鏈接存儲(chǔ)結(jié)構(gòu)相同，是通過(guò)由結(jié)點(diǎn)構(gòu)成的單

鏈表實(shí)現(xiàn)的，此時(shí)表頭指針被稱為棧頂指針，由棧頂指針指向的表頭結(jié)點(diǎn)被稱

為棧頂結(jié)點(diǎn)，整個(gè)單鏈表被稱為鏈棧，即鏈接存儲(chǔ)的棧。當(dāng)向一個(gè)鏈棧插入元

素時(shí)，是把該元素插入到棧頂，即使該元素結(jié)點(diǎn)的指針域指向原來(lái)的棧頂結(jié)

點(diǎn)，而棧頂指針則修改為指向該元素結(jié)點(diǎn)，使該結(jié)點(diǎn)成為新的棧頂結(jié)點(diǎn)。當(dāng)從

一個(gè)鏈棧中刪除元素時(shí)，是把棧頂元素結(jié)點(diǎn)刪除掉，即取出棧頂元素后，使棧

頂指針指向原棧頂結(jié)點(diǎn)的后繼結(jié)點(diǎn)。由此可知，對(duì)鏈棧的插入和刪除操作是在

單鏈表的表頭進(jìn)行的，其時(shí)間復(fù)雜度為0(1)。

設(shè)一個(gè)棧為(a,b,c),當(dāng)采用鏈接存儲(chǔ)時(shí)，對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)示意圖如圖4-

2(a)所示，其中HS表示棧頂指針，其值為存儲(chǔ)元素c結(jié)點(diǎn)的地址。當(dāng)向這個(gè)棧

插入一個(gè)元素d后，對(duì)應(yīng)如圖4-2(b)所示。當(dāng)從這個(gè)棧依次刪除兩個(gè)元素后，

對(duì)應(yīng)如圖4-2(c)所示。當(dāng)鏈棧中的所有元素全部出棧后，棧頂指針HS的值為

空，即常量NULL所表示的數(shù)值0。

圖4-2棧的鏈接存儲(chǔ)結(jié)構(gòu)及操作過(guò)程

3.棧的抽象數(shù)據(jù)類型

棧的抽象數(shù)據(jù)類型中的數(shù)據(jù)部分為具有ElemType元素類型的一個(gè)棧，它可

以采用任一種存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)；操作部分包括元素進(jìn)棧、出棧、讀取棧頂元素、

檢查棧是否為空等。下面給出棧的抽象數(shù)據(jù)類型的具體定義。

ADTSTACKisData：

采用順序或鏈接方式存儲(chǔ)的棧，假定其存儲(chǔ)類型用StackType

標(biāo)識(shí)符表示。

Operation：

voidInitStack(StackType&S)；

〃初始化棧S,即把它置為空

voidClearStack(StackType&S)；

〃清除棧S中的所有元素，使之成為一個(gè)空棧

intStackEmpty(StackType&S)；

〃判定S是否為空，若是則返回1,否則返回0ElemType

Peek(StackType&S)

//返回S的棧頂元素，但不移動(dòng)棧頂指針

voidPush(StackType&S,constElemType&item)

〃元素item進(jìn)棧，即插入到棧頂

ElemTypePop(StackType&S)

〃刪除棧頂元素并返回之

intStackFull(Stack&S)

〃若棧已滿則返回1,否則返回0,此函數(shù)為順

//序存儲(chǔ)的棧所特有

endSTACK

對(duì)于判定棧是否為空和返回棧頂元素的兩種操作，由于它們不改變棧的狀

態(tài)，所以可在參數(shù)類型說(shuō)明前使用常量定義符const。

假定棧a的元素類型為int,下面給出調(diào)用上述棧操作的一些例子。

(1)InitStack(a)；〃把棧a置空

(2)Push(a,35)；〃元素35進(jìn)棧

(3)intx=48；Push(a,x)；//48進(jìn)棧

(4)Push(a,x/2)；//x除以2的值24進(jìn)棧

(5)x=Pop(a)；〃棧頂元素24退棧并賦給x

(6)x=Peek(a)；//讀取棧頂元素48并賦給x

(7)Pop(a);〃棧頂元素48退棧

(8)StackEmpty(a)；〃因棧非空，應(yīng)返回0

(9)coutPop(a)endl；〃棧頂元素35退棧并輸出

(10)x=StackEmpty(a)；〃因棧為空，應(yīng)返回1,然后賦給x4.棧運(yùn)算的實(shí)

現(xiàn)

棧運(yùn)算(操作)的具體實(shí)現(xiàn)取決于棧的存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)不同，其算法描

述也不同。下面分別給出棧的運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的具

體算法。

(a)棧的操作在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)

假定采用順序存儲(chǔ)結(jié)構(gòu)定義的棧用標(biāo)識(shí)符S表示，其類型為已經(jīng)給出過(guò)的

Stack記錄類型。

(1)初始化棧

voidInitStack(Stack&S)

〃初始化棧S,即把它置為空

S.top=-l；

)

⑵把一個(gè)棧清除為空

在順序存儲(chǔ)方式下，同初始化棧的算法相同。

voidClearStack(Stack&S)

〃清除棧S中的所有元素，使之成為一個(gè)空棧

{

S.top=~l；

)

(3)檢查一個(gè)棧是否為空

intStackEmpty(Stack&S)

〃判定S是否為空，若是則返回1,否則返回0

{

returnS.top==-l；

)

(5)讀取棧頂元素

ElemTypePeek(StackType&S)

〃返回S的棧頂元素，但不移動(dòng)棧頂指針

{

〃若棧為空則終止程序運(yùn)行

if(S.top==~l){

cerr"Stackisempty!”endl；

exit(1)；

〃返回棧頂元素的值

returnS.stack[S.top]；

)

(5)向棧中插入元素

voidPush(Stack&S,constElemType&item)

〃元素item進(jìn)棧，即插入到棧頂

{

〃若棧己滿則終止程序運(yùn)行

if(S.top==StackMaxSize-1){

cerr'Stackoverflow!”endl；

exit(1)；

)

〃將棧頂指針后移一個(gè)位置

S.top++；

〃將item的值賦給新的棧頂位置

S.stack[S.top]=item；

)

(6)從棧中刪除元素

ElemTypePop(StackType&S)

〃刪除棧頂元素并返回之

〃若棧為空則終止程序運(yùn)行

if(S.top==~l){

cerr"Stackisempty!”endl；

exit(1)；

〃暫存棧頂元素以便返回

ElemTypetemp=S.stack[S.top]；

〃棧頂指針前移一個(gè)位置

S.top一；

〃返回原棧頂元素的值

returntemp；

從出棧算法可以看出，原棧頂元素的值沒(méi)有被改變，所以可以不使用臨時(shí)

變量保存它，返回語(yǔ)句中返回S.stack[S.top+1]的值即可。

(7)檢查棧是否已滿

intStackFull(Stack&S)

〃若棧已滿則返回1,否則返回0,此函數(shù)為順序棧所特有

returnS.top==StackMaxSize-l；

(b)棧的操作在鏈接存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)

假定鏈棧中的結(jié)點(diǎn)仍采用在第二章中已經(jīng)定義的LNode結(jié)點(diǎn)類型，并假定

棧頂指針用HS表示，下面給出對(duì)由HS所指向的鏈棧進(jìn)行每一種棧操作的算

法。

(1)初始化鏈棧

voidInitStack(LNode*&HS)

HS=NULL；〃將鏈棧置空。

⑵清除鏈棧為空

voidClearStack(LNode*&HS)

{

LNode*cp,*np；

〃用cp作為指向待刪除的結(jié)點(diǎn)，np指向cp的后繼結(jié)點(diǎn)。

cp=HS；〃給cp指針賦初值，使之指向棧頂結(jié)點(diǎn)。

while(cp!=NULL)

{〃從棧頂?shù)綏５滓来蝿h除每個(gè)結(jié)點(diǎn)

np=cp-next；

deletecp；

cp=np；

)

HS=NULL；〃置鏈棧為空

)

⑶檢查鏈棧是否為空

intStackEmpty(LNode*HS)

//HS為值參或引用形參均可

(

returnHS==NULL；

}

(4)讀取棧頂元素

ElemTypePeek(LNode*HS)//HS為值參或引用形參均可

{

if(HS==NULL){

cerr"Linkedstackisempty!”endl；

exit(1)；

returnHS-data；

⑸向鏈棧中插入一個(gè)元素

voidPush(LNode*&HS,constElemType&item)

{

〃為插入元素獲取動(dòng)態(tài)結(jié)點(diǎn)

LNode*newptr=newLNode；

if(newptr==NULL){

cerr^Memoryallocationfailare!〃endl；

exit(1)；

)

〃給新分配的結(jié)點(diǎn)賦值

newptr-data=item；

〃向棧頂插入新結(jié)點(diǎn)

newptr-next=HS；

HS=newptr；

)

(6)從鏈棧中刪除一個(gè)元素

ElemTypePop(LNode*&HS)

(

if(HS==NULL){

cerr"Linkedstackisempty!”endl；

exit(1)；

)

LNode*p=HS；〃暫存棧頂結(jié)點(diǎn)

HS=HS-next；〃使棧頂指針指向其后繼結(jié)點(diǎn)

ElemTypetemp=p~data；〃暫存原棧頂元素

deletep；〃回收原棧頂結(jié)點(diǎn)

returntemp；〃返回原棧頂元素

)

5.棧的簡(jiǎn)單應(yīng)用舉例

例L從鍵盤上輸入一批整數(shù)，然后按照相反的次序打印出來(lái)。

根據(jù)題意可知，后輸入的整數(shù)將先被打印出來(lái)，這正好符合棧的后進(jìn)先出

的特點(diǎn)。所以此題很輕易用棧來(lái)解決。參考程序如下：

Sincludeiostream,h

Sincludestdlib.hconstintStackMaxSize=30；

typedefintElemType；〃定義元素類型為整型

structStack{

ElemTypestack[StackMaxSize]；

inttop；

);

Sinclude^stack.h〃

〃假定對(duì)順序棧操作的算法已經(jīng)存于〃stack,h〃頭文件中

voidmain()

Stacka；

InitStack(a)；

intx；

cinx；

while(x!=-l){

〃假定用T作為終止鍵盤輸入的標(biāo)志，輸入的整數(shù)個(gè)數(shù)

〃不能超過(guò)StackMaxSize所規(guī)定的值

Push(a,x)；

cinx；

)

while(!StackEmpty(a))〃棧不為空時(shí)依次退棧打印出來(lái)

coutPop(a)""；

coutendl；

)

假定從鍵盤上輸入為：

786345829134-1

則輸出為：

349182456378

例2.堆棧在計(jì)算機(jī)語(yǔ)言的編譯過(guò)程中用來(lái)進(jìn)行語(yǔ)法檢查，試編寫一個(gè)算

法，用來(lái)檢查一個(gè)C++語(yǔ)言程序中的花括號(hào)、方括號(hào)和圓括號(hào)是否配對(duì)，若能

夠全部配對(duì)則返回1,否則返回0。

在這個(gè)算法中，需要掃描待檢查程序中的每一個(gè)字符，當(dāng)掃描到每個(gè)花、

中、圓左括號(hào)時(shí)，令其進(jìn)棧，當(dāng)掃描到每個(gè)花、中、圓右括號(hào)時(shí)，則檢查棧頂

是否為相應(yīng)的左括號(hào)，若是則作退棧處理，若不是則表明出現(xiàn)了語(yǔ)法錯(cuò)誤，應(yīng)

返回0。當(dāng)掃描到程序文件結(jié)尾后，若棧為空則表明沒(méi)有發(fā)現(xiàn)括號(hào)配對(duì)錯(cuò)誤，

應(yīng)返回1,否則表明棧中還有未配對(duì)的括號(hào)，應(yīng)返回0。另外，對(duì)于一對(duì)單引號(hào)

或雙引號(hào)內(nèi)的字符不進(jìn)行括號(hào)配對(duì)檢查。

根據(jù)分析，編寫出算法如下：

intBracketsCheck(char*fname)

〃對(duì)由fname所指字符串為文件名的文件進(jìn)行括號(hào)配對(duì)檢查

(

ifstreamifstr(fname,ios：in|ios：nocreate)；

〃用文件輸入流對(duì)象ifstr打開以fname所指字符串為文件名的文件

if(!ifstr){

cerrFile\fname\notfound!endl；

exit(1)；

)

Stacka；〃定義一個(gè)順序棧

InitStack(a)；〃棧a初始化

charch；

while(ifstrch)〃順序掃描文件中的每一個(gè)字符

{

if(ch==39){〃單引號(hào)內(nèi)的字符不參與配對(duì)比較

while(ifstrch)

if(ch==39)//39為單引號(hào)的ASCH值

break；

if(!ifstr)

return0；

)

elseif(ch==34){〃雙引號(hào)內(nèi)的字符不參與配對(duì)比較

while(ifstrch)

if(ch==34)//34為雙引號(hào)的ASCH值

break；

if(!ifstr)

return0；

)

switch(ch)

case

case

case，('：

Push(a,ch)；〃出現(xiàn)以上三種左括號(hào)則進(jìn)棧

break；

case，}‘：

if(Peek(a)==,{')

Pop(a)；〃棧頂?shù)淖蠡ɡㄌ?hào)出棧

elsereturn0；

break；

case，］'：

if(Peek(a)==，V)

Pop(a)；〃棧頂?shù)淖笾欣ㄌ?hào)出棧

elsereturn0；

break；

case，)’：

if(Peek(a)二二'(')

Pop(a)；〃棧頂?shù)淖髨A括號(hào)出棧

elsereturn0；

)

)

if(StackEmpty(a))

return1；

elsereturn0；

例3.把十進(jìn)制整數(shù)轉(zhuǎn)換為二至九之間的任一進(jìn)制數(shù)輸出。

由計(jì)算機(jī)基礎(chǔ)知識(shí)可知，把一個(gè)十進(jìn)制整數(shù)X轉(zhuǎn)換為任一種r進(jìn)制數(shù)得到

的是一個(gè)r進(jìn)制的整數(shù)，假定為y,轉(zhuǎn)換方法是逐次除基數(shù)r取余法。具體敘

述為：首先用十進(jìn)制整數(shù)x除以基數(shù)r,得到的整余數(shù)是r進(jìn)制數(shù)y的最低位

yO,接著以x除以r的整數(shù)商作為被除數(shù)，用它除以r得到的整余數(shù)是y的次

最低位yl,依次類推，直到商為。時(shí)得到的整余數(shù)是y的最高位ym,假定y共

有m+1位。這樣得到的y與x等值，y的按權(quán)展開式為：

y=yO+yl.r+y2.r2+.+ym.rm

例如，若十進(jìn)制整數(shù)為3425,把它轉(zhuǎn)換為八進(jìn)制數(shù)的過(guò)程如圖4-3所示。

圖4-3十進(jìn)制整數(shù)3425轉(zhuǎn)換為八進(jìn)制數(shù)的過(guò)程

最后得到的八進(jìn)制數(shù)為(6541)8,對(duì)應(yīng)的十進(jìn)制數(shù)為6X83+5X82+4X

8+1=3425,即為被轉(zhuǎn)換的十進(jìn)制數(shù)，證實(shí)轉(zhuǎn)換過(guò)程是正確的。

從十進(jìn)制整數(shù)轉(zhuǎn)換為r進(jìn)制數(shù)的過(guò)程中，由低到高依次得到r進(jìn)制數(shù)中的

每一位數(shù)字，而輸出時(shí)又需要由高到低依次輸出每一位。所以此問(wèn)題適合利用

棧來(lái)解決，具體算法描述為：

voidTransform(longnum,intr)

〃把一個(gè)長(zhǎng)整型數(shù)num轉(zhuǎn)換為一個(gè)r進(jìn)制數(shù)輸出

(

Stacka；〃利用棧a存儲(chǔ)轉(zhuǎn)換后得到的每一位數(shù)字

InitStack(a)；〃初始化棧

while(num!=0)

{〃由低到高求出r進(jìn)制數(shù)的每一位并入棧

intk=num%r；

Push(a,k)；

num/=r；

while(!StackEmpty(a))〃由高到低輸出r進(jìn)制數(shù)的每一位

coutPop(a)；

coutendl；

假定用下面的主程序調(diào)用Transform過(guò)程。

voidmain()

(

cout”3425的八進(jìn)制數(shù)為：”；

Transform(3425,8)；

cout”3425的六進(jìn)制數(shù)為：”；

Transform(3425,6)；

cout”3425的四進(jìn)制數(shù)為：”；

Transform(3425,4)；

cout”3425的二進(jìn)制數(shù)為：”；

Transform(3425,2)；

)

則得到的運(yùn)行結(jié)果如下：

3425的八進(jìn)制數(shù)為：65413425的六進(jìn)制數(shù)為：235053425的四進(jìn)制數(shù)

為：3112013425的二進(jìn)制數(shù)為：110101100001

二、算術(shù)表達(dá)式的計(jì)算

在計(jì)算機(jī)中進(jìn)行算術(shù)表達(dá)式的計(jì)算是通過(guò)棧來(lái)實(shí)現(xiàn)的。這一節(jié)首先討論算

術(shù)表達(dá)式的兩種表示方法，即中綴表示法和后綴表示法，接著討論后綴表達(dá)式

求值的算法，最后討論中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法。

1.算術(shù)表達(dá)式的兩種表示

通常書寫的算術(shù)表達(dá)式是由操作數(shù)(又叫運(yùn)算對(duì)象或運(yùn)算量)和運(yùn)算符以及

改變運(yùn)算次序的圓括號(hào)連接而成的式子。操作數(shù)可以是常量、變量和函數(shù)，同

時(shí)還可以是表達(dá)式。運(yùn)算符包括單目運(yùn)算符和雙目運(yùn)算符兩類，單目運(yùn)算符只

要求一個(gè)操作數(shù)，并被放在該操作數(shù)的前面，雙目運(yùn)算符要求有兩個(gè)操作數(shù)，

并被放在這兩個(gè)操作數(shù)的中間。單目運(yùn)算符為取正'+'和取負(fù)'」，雙目運(yùn)算符

有加減乘'*'和除'/'等。為了簡(jiǎn)便起見，在我們的討論中只考慮雙目

運(yùn)算符。

如對(duì)于一個(gè)算術(shù)表達(dá)式2+5*6,乘法運(yùn)算符'*'的兩個(gè)操作數(shù)是它兩邊的5

和6；對(duì)于加法運(yùn)算符'+'的兩個(gè)操作數(shù)，一個(gè)是它前面的2,另一個(gè)是它后面

的5*6的結(jié)果即30o我們把雙目運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)中間的這種習(xí)慣表示

叫做算術(shù)表達(dá)式的中綴表示，這種算術(shù)表達(dá)式被稱為中綴算術(shù)表達(dá)式或中綴表

達(dá)式。

中綴表達(dá)式的計(jì)算比較復(fù)雜，它必須遵守以下三條規(guī)則：

(1)先計(jì)算括號(hào)內(nèi)，后計(jì)算括號(hào)外；

(2)在無(wú)括號(hào)或同層括號(hào)內(nèi)，先進(jìn)行乘除運(yùn)算，后進(jìn)行加減運(yùn)算，即乘除運(yùn)

算的優(yōu)先級(jí)高于加減運(yùn)算的優(yōu)先級(jí)；

(3)同一優(yōu)先級(jí)運(yùn)算，從左向右依次進(jìn)行。

從這三條規(guī)則可以看出，在中綴表達(dá)式的計(jì)算過(guò)程中，既要考慮括號(hào)的作

用，又要考慮運(yùn)算符的優(yōu)先級(jí)，還要考慮運(yùn)算符出現(xiàn)的先后次序。因此，各運(yùn)

算符實(shí)際的運(yùn)算次序往往同它們?cè)诒磉_(dá)式中出現(xiàn)的先后次序是不一致的，是不

可猜測(cè)的。當(dāng)然憑直觀判別一個(gè)中綴表達(dá)式中哪個(gè)運(yùn)算符最先算，哪個(gè)次

之，…，哪個(gè)最后算并不困難，但通過(guò)計(jì)算機(jī)處理就比較困難了，因?yàn)橛?jì)算機(jī)

只能一個(gè)字符一個(gè)字符地掃描，要想得到哪一個(gè)運(yùn)算符先算，就必須對(duì)整個(gè)中

綴表達(dá)式掃描一遍，一個(gè)中綴表達(dá)式中有多少個(gè)運(yùn)算符，原則上就得掃描多少

遍才能計(jì)算完畢，這樣就太浪費(fèi)時(shí)間了，顯然是不可取的。

那么，能否把中綴算術(shù)表達(dá)式轉(zhuǎn)換成另一種形式的算術(shù)表達(dá)式，使計(jì)算簡(jiǎn)

單化呢？回答是肯定的。波蘭科學(xué)家盧卡謝維奇(Lukasiewicz)很早就提出了算

術(shù)表達(dá)式的另一種表示，即后綴表示，又稱逆波蘭式，其定義是把運(yùn)算符放在

兩個(gè)運(yùn)算對(duì)象的后面。采用后綴表示的算術(shù)表達(dá)式被稱為后綴算術(shù)表達(dá)式或后

綴表達(dá)式。在后綴表達(dá)式中，不存在括號(hào)，也不存在優(yōu)先級(jí)的差別，計(jì)算過(guò)程

完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行，整個(gè)計(jì)算過(guò)程僅需一遍掃描便可完成，

顯然比中綴表達(dá)式的計(jì)算要簡(jiǎn)單得多。例如，對(duì)于后綴表達(dá)式12!4!-!5!

/，其中‘！'字符表示成分之間的空格，因減法運(yùn)算符在前，除法運(yùn)算符在后，

所以應(yīng)先做減法，后做除法；減法的兩個(gè)操作數(shù)是它前面的12和4,其中第一

個(gè)數(shù)12是被減數(shù)，第二個(gè)數(shù)4是減數(shù)；除法的兩個(gè)操作數(shù)是它前面的12減4

的差(即8)和5,其中8是被除數(shù)，5是除數(shù)。

中綴算術(shù)表達(dá)式轉(zhuǎn)換成對(duì)應(yīng)的后綴算術(shù)表達(dá)式的規(guī)則是：把每個(gè)運(yùn)算符都

移到它的兩個(gè)運(yùn)算對(duì)象的后面，然后刪除掉所有的括號(hào)即可。

例如，對(duì)于下列各中綴表達(dá)式：

(1)3/5+6

(2)16-9*(4+3)

(3)2*(x+y)/(l-x)

(4)(25+x)*(a*(a+b)+b)

對(duì)應(yīng)的后綴表達(dá)式分別為：

(1)3!5!/!6!+

(2)16!9!4!3!+!*!-

(3)2!x!y!+!*!1!x!-!/

(4)25!x!+!a!a!b!+!*!b!+!*

2.后綴表達(dá)式求值的算法

后綴表達(dá)式的求值比較簡(jiǎn)單，掃描一遍即可完成。它需要使用一個(gè)棧，假

定用S表示，其元素類型應(yīng)為操作數(shù)的類型，假定為浮點(diǎn)型float,用此棧存

儲(chǔ)后綴表達(dá)式中的操作數(shù)、計(jì)算過(guò)程中的中間結(jié)果以及最后結(jié)果。假定一個(gè)后

綴算術(shù)表達(dá)式以字符作為結(jié)束符，并且以一個(gè)字符串的方式提供。后綴表達(dá)

式求值算法的基本思路是：把包含后綴算術(shù)表達(dá)式的字符串定義為一個(gè)輸入字

符串流對(duì)象，每次從中讀入一個(gè)字符(空格作為數(shù)據(jù)之間的分隔符，不會(huì)被作為

字符讀入)時(shí)，若它是運(yùn)算符，則表明它的兩個(gè)操作數(shù)已經(jīng)在棧S中，其中棧頂

元素為運(yùn)算符的后一個(gè)操作數(shù)，棧頂元素的下一個(gè)元素為運(yùn)算符的前一個(gè)操作

數(shù)，把它們彈出后進(jìn)行相應(yīng)運(yùn)算即可，然后把運(yùn)算結(jié)果再壓入棧S中；否則，

讀入的字符必為操作數(shù)的最高位數(shù)字，應(yīng)把它重新送回輸入流中，然后把下一

個(gè)數(shù)據(jù)作為浮點(diǎn)數(shù)輸入，并把它壓入到棧S中。依次掃描每一個(gè)字符(對(duì)于浮點(diǎn)

數(shù)只需掃描它的最高位并一次輸入整個(gè)浮點(diǎn)數(shù))并進(jìn)行上述處理，直到碰到結(jié)束

符'@'為止，表明后綴表達(dá)式計(jì)算完畢，最終結(jié)果保存在棧中，并且棧中僅存這

一個(gè)值，把它彈出返回即可。具體算法描述為：

floatCompute(char*str)

〃計(jì)算由str字符串所表示的后綴表達(dá)式的值，

〃表達(dá)式要以字符結(jié)束。

StackS；〃用S棧存儲(chǔ)操作數(shù)和中間計(jì)算結(jié)果

InitStack(S)；//初始化棧

istrstreamins(str)；〃把str定義為輸入字符串流對(duì)象inscharch；

〃用于輸入字符

floatx；〃用于輸入浮點(diǎn)數(shù)

insch；〃從ins流對(duì)象(即str字符串)中順序讀入一個(gè)字符