目錄

1概述................................................................2

1.1目的及意義..................................................................2

2系統(tǒng)分析..........................................................................2

2.1需求分析.....................................................................2

3概要設(shè)計(jì)..........................................................................2

3.1系統(tǒng)總體結(jié)構(gòu)............................................................2

3.2程序算法圖.................................................................2

4詳細(xì)設(shè)計(jì)..........................................................................3

4.1中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式.............................................3

4.1.1求運(yùn)算符優(yōu)先級(jí)函數(shù)...............................................4

4.1.2輸出隊(duì)列.............................................................4

4.2后綴表達(dá)式的求值........................................................4

5運(yùn)行與測(cè)試........................................................................5

5.1輸入5

5.2輸出結(jié)果：.............................................................5

6總結(jié)和心得........................................................................6

6.1心得與問(wèn)題.................................................................6

6.2總結(jié)..................................................................6

參考文獻(xiàn)............................................................................6

1概述

1.1目的及意義

我們?cè)诤茉绲臅r(shí)候就開(kāi)始學(xué)習(xí)書(shū)寫(xiě)及計(jì)算表達(dá)式，可以說(shuō)運(yùn)用起來(lái)很熟練了，但有時(shí)候

并不想自己計(jì)算，交給計(jì)算器是時(shí)有的事，然而普通的計(jì)算器并不懂得優(yōu)先級(jí)，給計(jì)算帶來(lái)

了一定的不便。

本程序?qū)崿F(xiàn)的目的是將人們習(xí)慣的中綴表達(dá)式轉(zhuǎn)換為計(jì)算機(jī)所能理解的后綴表達(dá)式以

方便計(jì)算，最終得出我們所需要的正確的答案。

2系統(tǒng)分析

2.1需求分析

當(dāng)我們需要進(jìn)行一長(zhǎng)串的計(jì)算時(shí)，各種運(yùn)算符夾雜在一起，通過(guò)筆算很容易得出結(jié)果。

然而計(jì)算機(jī)并沒(méi)有人腦那末聰明，它并不懂得先乘除后加減，有括號(hào)要先計(jì)算括號(hào)里面的，

它只知道從左到右的進(jìn)行計(jì)算，這就造成為了計(jì)算機(jī)計(jì)算的失誤，科學(xué)的計(jì)算是人們非常需

要

的計(jì)算工具。

3概要設(shè)計(jì)

3.1系統(tǒng)總體結(jié)構(gòu)

整個(gè)系統(tǒng)結(jié)構(gòu)如圖3-1-1所示，結(jié)構(gòu)非常清晰，程序順序執(zhí)行，首先提示用戶(hù)輸入需要

計(jì)算的表達(dá)式，經(jīng)過(guò)轉(zhuǎn)換得到后綴表達(dá)式，最后結(jié)果將數(shù)據(jù)顯示到主屏幕上即可。

圖3.1.1系統(tǒng)總體結(jié)構(gòu)圖

3.2程序算法圖

本程序所用的數(shù)據(jù)結(jié)構(gòu)類(lèi)型是棧和隊(duì)列。

2/11

首先提示用戶(hù)輸入中綴表達(dá)式，再利用程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，其中數(shù)字

入隊(duì)列，算術(shù)運(yùn)算符入棧。

圖3.2.1程序算法圖

4詳細(xì)設(shè)計(jì)

4.1中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式首先需要掃描中綴表達(dá)式，當(dāng)遇到數(shù)字時(shí)，將其入隊(duì)列，

當(dāng)遇到運(yùn)算符時(shí)，若是低優(yōu)先級(jí)則直接入棧，若是高優(yōu)先級(jí)則將低優(yōu)先級(jí)運(yùn)算符彈出，并

入隊(duì)列，再將此次運(yùn)算符入棧，最終形成后綴表達(dá)式

圖4.1.1后綴表達(dá)式的轉(zhuǎn)換

其偽代碼算法如下：

switch(c){

caseOtocase:ErQeceQc)

ca^'(*:Rdi(S,c)

case*)t=Rp(S);

if(t!=r('&&t!=T#')

EnQueue(Q,t);

}v^iile(t!=f。&&S->tcp!-l);

ca?*+*||ca?—11ca^**'IIcase71:

while(Priority(c)<=Priority(GetTcp(S)))〃比較優(yōu)先級(jí)

EnQueue(Q,Pop(S))

Push⑸c)

)

3/11

4.1.1求運(yùn)算符優(yōu)先級(jí)函數(shù)

算術(shù)運(yùn)算符入棧時(shí)必須考慮運(yùn)算符的優(yōu)先級(jí)，才干形成正確的后綴表達(dá)式，當(dāng)讀到運(yùn)算

符時(shí)，將棧中所有優(yōu)先級(jí)高于或者等于該運(yùn)算符的運(yùn)算符彈出，送至輸出隊(duì)列中，再將當(dāng)前

運(yùn)算符入棧；當(dāng)讀入左括號(hào)時(shí)，即入棧；當(dāng)讀到右括號(hào)時(shí)，將挨近棧頂?shù)牡谝粋€(gè)左括號(hào)上

面的

運(yùn)算符全部挨次彈出，送至輸出隊(duì)列中，再刪除棧中的左括號(hào)。

通過(guò)返回值的大小代表優(yōu)先級(jí)的大小，其偽代碼算法如下：

switch(cp){

casef(f|lease*#*:O;h?k;

ca^*-f||ca^l/kxeek;

case*11ca^，八return2;teak;

)

4.1.2輸出隊(duì)列

之中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式之后，需要輸出后綴表達(dá)式，也就是當(dāng)前隊(duì)列，只需要

讓頭指針遍歷輸出數(shù)據(jù)即可。

其偽代碼如下：

x=Q->data[Q->front-H-];

4.2后綴表達(dá)式的求值

由于在將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式時(shí)已經(jīng)將運(yùn)算符安排在了合適的位置，在后綴表

達(dá)式中不僅不需要括號(hào)，而且還徹底免除了運(yùn)算符優(yōu)先規(guī)則，僅需從左到右計(jì)算即可。

其偽代碼如下：

while(!QueueEnpty(Q)){

ch=DeQueue(Q)

if(ch>='0'&&ch<=g)

⑸dyU;)〃數(shù)字字符到數(shù)值的轉(zhuǎn)換

else{

y=Pop(S),x=Pop(S)

switch(ch){

11

case+：Pu^i(Szx+y);break;

case:Rash(S,xf);break;

case:Push(Szx*y);break;

ca^71:Pu±i(S,Wy);break;

)

}

4/11

5運(yùn)行與測(cè)試

5.1輸入表達(dá)式:

輸入一個(gè)中綴表達(dá)式:

5.2輸出結(jié)果:

輸出后綴表達(dá)式及其結(jié)果:

5/11

6總結(jié)和心得

6.1心得與問(wèn)題

在本次實(shí)驗(yàn)中，遇到的心得：

①為什么有判空隊(duì)列不需要判空棧？因?yàn)楫?dāng)S->top=-l時(shí)棧變?yōu)榭?，不需要單?dú)寫(xiě)一

個(gè)函數(shù)出來(lái)判斷。

②后綴表達(dá)式的求值中，Push(S,ch-，O，)中的ch-。是什么意思？因?yàn)檩斎氡磉_(dá)式時(shí)數(shù)

字是以字符的形式存儲(chǔ)的，當(dāng)進(jìn)行計(jì)算式需要字符到數(shù)值的轉(zhuǎn)換。

③中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式時(shí)為什么要用Push(S,W)將#壓入棧底？

④后綴表達(dá)式的求值中，SeqStackvs的作用是什么？為什么不用vs會(huì)出錯(cuò)？

⑤調(diào)用后綴表達(dá)式進(jìn)行計(jì)算時(shí)，最終計(jì)算結(jié)果是放在棧中的，但為什么返回棧頂元素

時(shí)總是指向空？因?yàn)橹罢{(diào)用了Dequeue(Q),導(dǎo)致front發(fā)生了改變，相當(dāng)于隊(duì)列

被刪除了，所以再調(diào)用時(shí)就為空了，解決方法有多種，比如復(fù)制隊(duì)列，我采取了一

個(gè)簡(jiǎn)單的方法，在調(diào)用了CTPostExp(Q)后不忙著輸出后綴表達(dá)式，繼續(xù)調(diào)用

CPostExp(Q),在CPostExp(Q)中使用Dequeue(Q)時(shí)順便就將后綴表達(dá)式輸出，這樣

就避免了隊(duì)列第二次調(diào)用時(shí)已經(jīng)被刪除的窘境。

6.2總結(jié)

本次試驗(yàn)中內(nèi)存出錯(cuò)的情況比較多，比如在輸出后綴表達(dá)式時(shí)雖然結(jié)果正確，但后面還

有不少“燙燙…”，在計(jì)算后綴表達(dá)式時(shí)，返回值總是沒(méi)有，等等，但通過(guò)不斷地調(diào)試這些

問(wèn)題都得以解決。

通過(guò)本次實(shí)驗(yàn)，加強(qiáng)了對(duì)棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)的理解，特別是棧的先進(jìn)后出的結(jié)構(gòu)有了

更深的了解。

參考文獻(xiàn)

[1]蘇仕華等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).機(jī)械工業(yè)出版社.2005.05

[2]嚴(yán)蔚敏，吳偉明.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).清華大學(xué)出版社.2022

[3]譚浩強(qiáng).C程序設(shè)計(jì)(第三版).清華大學(xué)出版社.2005

附加程序代碼：

#include<stdio.h>

?defineStacksize100

#defineQueueSize100

typedefcharDataType;

typedefstruct

{

6/11

dhardata[100];

intfront,rear;

}SeqQueue;〃定義隊(duì)列類(lèi)型

typedefstruct

{

EataTypedata[100];

inttcp;

}SeqStack;〃棧類(lèi)型的定義

〃初始化隊(duì)列

voidInitQueue(Seqiieue*Q)

(

Q->front=0;

Q->rear=0;〃頭部和尾部份別賦值為0

}

〃清空隊(duì)列

intQueueEnpty(SeqQueue*Q)

(

returnQ->rear=Q->frcnt;〃隊(duì)列的頭指針等于尾指針

)

〃入隊(duì)列

voidEnQueue(SeqQueue*Q,DataTypex)

{

if((Q->rear+l)%QueueSize=Q->front)//判斷隊(duì)列是否裝滿(mǎn)

隊(duì)列溢出

else

(

Q->data[Q->rear]“

Q->rear=(Q->rear+l)%QueueSize;

)

)

〃輸出隊(duì)列

charDeQueue(SeqQueue*Q)

{

charx;

x=Q->data[Q->front];

Q->front++;

returnx;

}

//祕(mì)臺(tái)化棧

voidInitStack(Sec^tack*S)

(

S->tcp=-l;

}

7/11

〃入棧

voidPush(SeqStack*S,DataTypex)

{

if(S->tcp=StackSize-l)

棧溢出

else

(

S->tc^->tcp^l;//棧頂指針指向新插入的數(shù)據(jù)

S-X^ta[S->tcp]=x;

)

}

〃出棧

DataTypePop(SeqStack*S)

{

if(S->tcp=-l)

空棧

else

returnS->data[S->tcp-];

}

//取棧頂元素

DataTypeGetTop(SeqStack*S)

(

if(S->tcp=l)

?？?/p>

else

returnS-X^ta[S->tcp];

}

〃求運(yùn)算符優(yōu)先級(jí)函數(shù)

intPriority(EataTypeop)

(

switch(cp)

(

case1(*:

case:retum0;break;

ca^

ca^中l(wèi);br^k;

ca^

case'/〔return2;br^k;

)

)

//中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

voidCTPostExp(Sec^ueue*Q)

SeqStackOS;〃運(yùn)算符棧

8/11

charczt;

SeqStack*S;

S=&OSf

InitStack(S);

R^(S,'#');〃壓入棧底元素#

do〃掃描中綴表達(dá)式

(

c=getchar();

switch(c)

{

曰k;〃去除空格符

ca^'01:

casefl*:

ca^*2*:

ca^,3,:

ca^⑷：

ca^r51:

ca^*6,:

ca^7:

ca^8:

ca^9:

EnQueue(Q,c);break;

case'('：RJ?I(S,C);break;

ca^

ca^

do

(

t=Psp(S);

if(t!=?(f

EnQueue(Q,t);

}vhile(t!=*(*&&S->tcpH);break;

case

ca^

ca^

ca^71:

vhile(Priority(c)<=Priority(fetTcp(S)))〃比較優(yōu)先級(jí)

{

t=Pop(S);

EnQueue(Qzt);

)

Push(S,c);

break;

}

}vbile(c!=,#');

9/11

〃后綴表達(dá)式的求值

intCPostExp(SeqQueue*Q)

(

SeqStackvs,*S;

charch;

intxzy;

S=&vs;〃有什么用

InitS