2023年數(shù)據(jù)結構大作業(yè)

電子與信息工程學院

數(shù)據(jù)結構大作業(yè)

系別:電子與信息工程學院

班級:_____________

姓名：_______________

學號：____________

指導教師：_________

數(shù)據(jù)結構實驗報告

一、實驗目的

表達式求值。

一個算術表達式是由操作數(shù)、運算符和界線符組成。假設操作數(shù)是正整數(shù)，

運算符只含加減乘除四種運算符，界線符有左右括號和表達式起始、結束符

規(guī)定從鍵盤讀入一個合法的算術表達式，輸出對的的結果，并顯示輸入序列。

二、數(shù)據(jù)結構設計

任何一個表達式都是由操作符，運算符和界線符組成的。我們分別用順序棧

來寄存表達式的操作數(shù)和運算符。棧是限定于緊僅在表尾進行插入或刪除操作的

線性表。順序棧的存儲結構是運用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)?/p>

數(shù)據(jù)元素，同時附設棧頂指針指示棧頂元素在順序棧中的位置，棧底為棧底指針,

在順序棧中，它始終指向棧底，即棧頂指針=棧底指針可作為?？盏臉擞洠慨敳迦?/p>

新的棧頂元素時，棧頂指針增1,刪除棧頂元素時，棧底指針減1。

三、總體設計

1.一方面置操作數(shù)棧為空棧，表達式起始符"#"為運算符棧的棧底元素；

2.依次讀入表達式，若是操作符即進棧，若是運算符則和棧的棧頂運算符比

較優(yōu)先權后作相應的操作，直至整個表達式求值完畢（即棧的棧頂元素和當前讀

入的字符均為”#"）。

四、重栗界面

主界面

輸入3+5#后:

裝

譽

可以迸行加減乘除運算。

請

簫

奧糜俁襄際

運y

程結集=8_00

序結策，按任意鍵退出，

輸入(3+2)*(4+1)/2后:

?'?'FC:\UsersS\Administrator\Documents\c.exe|o|卜目-1|w￡3?]

-以

<

:X<35>tt

Z5*

>X4+12tt

幺

在S.1

=

一

呈S

2.按

鄉(xiāng)

口.

，

五、心得體會

通過設計表達式求值這個程序,我學到了很多知識，對堆棧的應用更加純熟,

也對程序設計有了新的見解。雖然設計過程當中碰到了很多困難，但我通過查資

料,請教同學都一一成功的解決了，最總完畢了他的設計,我感覺通過他我學到了

很多。

六、附錄源程序：

#include<stdio.h>

#inc1ude<stdlib.h>

#include<dos.h>

#inc1ude<conio,h>

#defineMAX10〃定義堆棧最大容量

voidpush_opnd(char);〃操作數(shù)堆棧入棧操作

floatpop_opnd()；〃操作數(shù)堆棧出棧操作

voidpush_optr(char);〃操作符堆棧入棧操作

charpop_optr()；〃操作符堆棧出棧操作

charre1ation(char,char);//比較兩個操作符的優(yōu)先級

floatoperate(float,char,float);//運算

f1oatopndlMAXJ;//操作數(shù)堆棧

charoptr[MAX1;〃操作符堆棧

inttopd=0;〃棧頂指針初始化

inttop=0;

charsymb[30]；〃表達式字符串

intmain()

{inti=0;

charsy;

floata,b；

printf（”本程序實現(xiàn)表達式求值的操作?？梢赃M行加減乘除運算。\n”）;

Printf（"這是堆棧應用的一個例子\n”）；

printf（”請輸入表達式（以#結束）:\n例如：3*（3+2）/5#\nn）；

push_optr(

gets(symb)；〃輸入表達式，以#為結束符

while((symb[i]!=,#1)||(optr[top]!='#'))

{if((symb[i]!=r+')&&(symb[i]!='-,)&&(symb[i]!='*')&&(symb

[i]!='〃)

&&(symb[i]!=*(*)&&(symb[i]!='),)&&(symb[i]!

=*#')&&(symb[i]!=z'))

{push_opnd(symb[i])；i++;}//假如當前字

符不是操作符，則入操作數(shù)棧，字符串指針加一

eIseswitch(relation(optr[top],symb[i]))〃若是操作

符，比較其和操作符棧的棧頂元素的優(yōu)先級

。{casef<':push_optr(symb[i]);i++;break;〃若棧頂元素優(yōu)

先級低，則當前字符入棧，指針加一

。case,=,:sy=pop_optr();i++;break;〃若優(yōu)先級相

等，必為兩個配對的括號，退棧，指針加一

case,>':sy=pop_optr();b=pop_opnd();

〃若優(yōu)先級高，則棧頂元素退棧，進行運算

a=pop_opnd();

—topd=topd+l;

opnd[topd]=operate(a,sy,b);〃把運算結果入棧

。break;

case'r:printf("語法錯誤！\n”);exit(0)；

)

)

printf("運算結果=%1.2f\n",opnd[topd]);

Printf("程序結束，按任意鍵退出！\n”)；

getch();

I

voidpush_opnd(charch)

{intch_i；

ch_i=ch-f0*;//把字符換算成數(shù)字，并入操作數(shù)棧

topd++;

opnd[topd]=ch_i；

floatpop_opnd()

{//操作數(shù)棧出棧

topd=topd—1;

returnopnd[topd+1];

)

voidpush_optr(charch)

{〃操作符入棧

top++;

optr[top]=ch：

)

charpop_optr()

{//操作數(shù)出棧

top------;

returnoptr[top+1];

)

charrelation(charsym1,charsym2)

{//比較兩個操作符的優(yōu)先級

inti；

charchl[2]；

intind[2];

charre[7][7]={>,<'，*<7,',">

o

o'>',>，,,<，,>',?>,

!>1,?>/>'/<1>,/>f,

。/>'/>'/

<—<?/<’

ch1[0]=sym1;

chi[1]=sym2；

for(i=0;i<=l;i++)

{switch(chi[i])

{case」'：ind[i]=0；break;

case'-*:ind[i]=1;break;

case'*':ind[i]=2;break;

case71:ind[i]=3；break；

case'('：ind[i]=4;break;

case