數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告：設(shè)計(jì)一個(gè)演示用運(yùn)算優(yōu)先法對(duì)算數(shù)表達(dá)式求值過程的程序

1、數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告：設(shè)計(jì)一個(gè)演 示用運(yùn)算優(yōu)先法對(duì)算數(shù)表達(dá)式 求值過程的程序。實(shí)習(xí)報(bào)告題目：設(shè)計(jì)一個(gè)演示用運(yùn)算優(yōu)先法對(duì)算數(shù)表達(dá)式求值過程的程序。班級(jí)：姓名：學(xué)號(hào)：完成日期：一、需求分析1建立運(yùn)算數(shù)棧SqStackl和運(yùn)算符棧SqStack2輔助分析算符有限關(guān) 系.2用戶輸入以“ #”結(jié)尾的算數(shù)表達(dá)式，本程序需要用戶自行輸入表 達(dá)式（運(yùn)算符可以是加（+）;減（-）;乘（*）;除（/）；括號(hào)（） 以字符形式讀入，在讀入的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)的識(shí)別處理， 在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。3在程序的適當(dāng)位置輸出運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作 的內(nèi)容，即演示運(yùn)算操作。4測(cè)

2、試數(shù)據(jù)見原題。5程序執(zhí)行的命令包括：（1）建立算數(shù)表達(dá)式；（2）得到運(yùn)算表達(dá)式的值；（3）演示運(yùn)算過程。二、概要設(shè)計(jì)1. 設(shè)定棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對(duì)象D = ai | ai charSet, i=1,2,n,n >0 數(shù)據(jù)關(guān)系:R1 = <ai-1, ai >| ai-1, ai D, i=2,n (約定an端為棧頂，al端為棧底)基本操作：InitStack (&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。Gettop(S, &e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂 元素。Push(&S,e)初始條件：棧S已存在。操

3、作結(jié)果：插入元素 e為新的棧頂元素。Pop(&S, &e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返 回其值。ADT Stack2. 本程序包括三個(gè)模塊(1) 主程序模塊：Void mai n()初始化;函數(shù)；(2) 棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型(3) 運(yùn)算模塊一一實(shí)現(xiàn)運(yùn)算并演示其過程模塊各模塊之間調(diào)用關(guān)系如下：棧模塊三、詳細(xì)設(shè)計(jì)1、元素類型、結(jié)點(diǎn)類型typedef structint *base;int *top;int stacksize;SqStack1;操作數(shù)棧typedef structchar *base;char *top;int stacksi

4、ze;SqStack2;操作符棧2、棧類型typedef structchar *base;char *top;int stacksize;Stack; 棧類型棧的基本操作設(shè)置如下：void In itStack(Stack &S)初始化，設(shè)S為空棧(S.top=NULL )Status GetTop(Stack S,ElemType e)若棧S不空，則以e帶回棧頂元素并返回TRUE，否則返回FALSEStatus Push(Stack&S,ElemType e)若分配空間成功，則在S的棧頂插入新的棧頂元素e,并返回TRUE，/否則返回FALSE其中部分操作的算法：Status

5、 Push(Stack & S,ElemType e)若分配空間成功，則在 S的棧頂插入新的棧頂元素e,并返回TRUE ； 否則棧不變，并返回FALSEif(MakeNode(p,e)P. next=S.top;S.top=p;S.size+;Retur n TRUE;else return FALSE;Status Pop(Stack & S,ElemType &e)若棧不空，則刪除S的棧頂元素并以e帶回其值，且返回TRUE，否則返回FALSE，且e無意義if(StackEmpty(S) return FALSE;elsep=S.top;S.top=S.top->

6、;n ext;e=p->:data;S.size-;return TRUE;3、運(yùn)算代碼int Operate(i nt a,char theta,i nt b) /計(jì)算表達(dá)式值：主要是將大的表達(dá)式轉(zhuǎn)化成小的表達(dá)式進(jìn)行逐步求值in t c;if(theta='+') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else c=a/b;return c;"/Operatein t result(SqStack1 *OPND,SqStack2 *OPTR) / 求值ch

7、ar a=0;char theta;int b,c ,nu mber=O;In tin itStack(OPND);Chari nitStack(OPTR);CharPush(OPTR,#);a=getchar();while(a!=# | CharGetTop(OPTR)!=#)printf(" 輸入字符：%c ",a);if(!In(a)/不是運(yùn)算符則進(jìn)棧nu mber=0;while(!I n(a)number = nu mber*10 +(a-48);/ 處z=10*x+ya = getchar();in tPush(OPND, nu mber);printf(&q

8、uot;主要操作：Push(OPND,%d) elseswitch(Precede(a,CharGetTop(OPTR) case '<':CharPush(OPTR,a); a=getchar();printf("主要操作：Push(OPTR,%c) break;case '=':CharPop(OPTR); a=getchar();printf("主要操作：Pop(OPTR,%c) break;case '>':theta=CharPop(OPTR);c=i ntPop(OPND); b=i ntPop(OPN

9、D);in tPush(OPND,Operate(b,theta,c); prin tf("主 要 操 作 ：理多位整數(shù)”,nu mber);,a);,a);Operate(%d,%c,%d)",b,theta,c);break;OPTR打印輸出表達(dá)式值prin tf("OPND棧：%d棧：%cn",lntGetTop(OPND),CharGetTop(OPTR);printf("The result is %d.n",IntGetTop(OPND); / return OK;4. 主函數(shù)和其他函數(shù)的代碼void ma in () /

10、主函數(shù)，使用自定義函數(shù)完成功能SqStack1 s1,*OPND;SqStack2 s2,*OPTR;OPND=&s1;OPTR=&s2;prin tf("Please en ter an expressi on with a end of '#'.n"); prin tf("The Expressi on:”)； result(OPND,OPTR);char Precede(char a,char b)/運(yùn)算優(yōu)先級(jí)判斷int i,j;char Table88='''+' '- '*&

11、#39; '/' '(' ')' '#''+ ''>''>''<''<''<''>''>'J J J J J J J J'''>''>''<''<''<''>''>' J J J J J J J

12、J'*''>''>''>''>''<''>''>'JJJJJJJJ'/''>''>''>''>''<''>''>'/，JJJJJJJ'(''<''<''<''<&#

13、39;'<''_''' JJJJJJJJ')''>''>''>''>''''>''>'/ J J J J J J J Jf f J J J J J J J J; /優(yōu)先級(jí)表格for(i_0;i<8;i+)if(Table0i_a) /縱坐標(biāo)尋找break;for(j_0;j<8;j+) /橫坐標(biāo)尋找if(Tablej0_b)break;return Tableji;i

14、nt ln(char c)/判斷c是否為操作符if ( c_'(' | c_'+' | c_'-' | c _ '*'| c_'/' | c_')' | c=# | c='A')return 1;/如果是操作符返回1elsereturn 0;/不是，返回05 .函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)： fmai nresultJ1 1 1(、 f Ini tStacPush GetTopInPrecede PopJ丿 l丿 I_) l丿 l丿 I四、調(diào)試分析算術(shù)表達(dá)式求值程序較為龐

15、大，調(diào)試花費(fèi)時(shí)間較多，主要是在for循環(huán)和while循環(huán)時(shí)容易出錯(cuò)，對(duì)于涉及的循環(huán)的操作開始和結(jié)束條件設(shè)置很關(guān)鍵。五、用戶手冊(cè)1. 本程序開發(fā)環(huán)境為VC 6.0，運(yùn)行環(huán)境為dos操作系統(tǒng)，執(zhí)行文件為：1.exe2. 運(yùn)行該程序后，產(chǎn)生如下圖所示的界面：3. 按照提示輸入一組表達(dá)式。4. 輸入完成后，按回車鍵。5. 屏幕上打印出對(duì)應(yīng)于該表達(dá)式的后綴表達(dá)式6. 打印表達(dá)式計(jì)算結(jié)果。72OFTN棧；tfIT|_楊« 媒<<131772S5ISriJV g D bktOfA找卞口' D ebul.exr '結(jié)具江5”Pircs any kiey 七 Q co n&

16、#39;t inue8)結(jié)果浪Press any keu to continue% £、測(cè)試結(jié)果1.OPHDffi： 8 OPT Utt- ft口 x蘭 7匸一0盤一石益 PJc-H7a.L7 丄 UE:? 燭-毘-扶4扶扶檸妓妓遞常式#熾施9子符：8主要操作| P*ish<OPND>口 XA.雷字字宇宇宇字字字 幕入A人人人人AAA表込式瑋X ：3*<7-2># 3 主要;* 主尊:=PushfOPHD =PushtOPTR,PushCOPTR ,PushtOPND,PushCOPTR .PusliCOPND Ope>'aite <75

17、PoP<0PTn1.5 Opeialze <3<>7>7y”2、OPHD OPND OPND OPND OPND OPND OPND OPHD OPHDOP7RJ|S. tOPTR cpin; CPTPJOPTRJ戔、- OPI曲戔i - OPIHJ! < OPIR3:-工 f * 一= 1 iaaaaaaaaaa表達(dá)式并以甘結(jié)尾.：1+2+3+4*1ttII:Push<OFND, L Puah<OrTn, i Push<OrND, :OpefAte<l, :Push<OPTH, :PusKOPND, i OpevA't

18、e 3:PusKOPTR, :PusKOPHD, :OperateCb,1>2>2>+,2>3>3>+3>4>4>+,4>OPND OPND112933G641U:-: I : : 戔戔戔夷夷戔戔戔戔W RRRRRRRRHt 叮叮叮 TTTTTTF PPPPPPPPPO 000000 0 00tt結(jié)卑Press 刊my key to centInue4.:ffsussw人表士于字i丈子1AAAAAAA表達(dá)式并以結(jié)尾.=1024/4*61(1主要王旻 王要 王要 王要Push(OPND,1024> Push<0PTR,4&g

19、t; Push(0PNDr4> Operate<1024, Push<OFTR,8> Push(OFND,8> Operatc<25S>*,8>OPMD= 1024 OPTA 棧:OPND： 1024 OPTE： Z OPND棧；4 OPTH棧；/"ND 桟；256 QFU1 棧； OPHDt 256 OPTfffJf « OFNDJt 8 OFTH檢 «OPHD棧：24 OPTRjft*結(jié)果：2049 -Press any key to c out in tie七、附錄源程序文件名清單:l.cpp /1 .exe

20、/stdio.h stdlib.h / stri ng.h / math.h /主程序可執(zhí)行文件/程序中用到的頭文件 程序中用到的頭文件 程序中用到的頭文件 程序中用到的頭文件程序代碼：#in clude<stdio.h>#in clude<stdlib.h>#in clude<stri ng.h>#in clude<math.h>#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10#defi ne ERROR 0#defi ne OK 1*棧彳typedef struct SqStack1

21、 運(yùn)算數(shù)棧int *base;int *top;int stacksize;SqStack1;typedef struct SqStack2 運(yùn)算符棧char *base;char *top;int stacksize;SqStack2;void Intln itStack(SqStack1 *S)S->base=(i nt *)malloc(STACK_INIT_SIZE*sizeof(i nt);if(!S->base) exit(ERROR);S->top二S->base;S->stacksize二STACK_INIT_SIZE;void Chari nit

22、Stack(SqStack2 *S)S->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S->base) exit(ERROR);S->top=S->base;S->stacksize=STACK_INIT_SIZE;int IntGetTop(SqStack1 *S) / 取棧頂元素int e;if(*S).top=(*S).base)return 0;e=*(*S).top-1);retur n e;char CharGetTop(SqStack2 *S) / 取棧頂元素char e;if(*S).t

23、op=(*S).base) return 0;e=*(*S).top-1);retur n e;int In tPush(SqStack1 *S,i nt e)*(*S).top+=e;retur n OK;int CharPush(SqStack2 *S,char e)*(*S).top+=e;retur n OK;int In tPop(SqStack1 *S)int e;if(*S).top=(*S).base) return 0;e=*-(*S).top;retur n e; int CharPop(SqStack2 *S)char e;if(*S).top=(*S).base) re

24、turn 0;e=*-(*s).top;retur n e;/*算模塊char Precede(char a,char b)/ 運(yùn)算優(yōu)先級(jí)判斷int i,j;char Table88=<''<''<# ,'V','V','V' /優(yōu)先級(jí)表格for(i=0;i<8;i+)if(TableOi=a) / 縱坐標(biāo)尋找break;for(j=0;j<8;j+) / 橫坐標(biāo)尋找if(Tablej0=b)break;retur n Tableji;int Operate© nt a,ch

25、ar theta, int b) /計(jì)算表達(dá)式值：主要是將大的表達(dá)式轉(zhuǎn)化成小的表達(dá)式進(jìn)行逐步求值int c;if(theta='+') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else c=a/b;return c;/Operateint In(char c)判斷c是否為操作符if ( c='(' | c='+' | c='-' | c = '*'| c='/' | c=')' | c='#'| c='A')elsereturn 0;不是，返回0int result(SqStack1 *0PND,SqStack2 *OPTR) / 求值char a=0;char theta;int b,c ,nu mber=0;Intln itStack(OPND);Chari nitStack(OPTR);CharPush(OPTR, '#');a=getchar();while(a!='#' | CharGetTop(OPTR)!二'#')printf("輸入字符：%c "