1、淮 海 工 學(xué) 院 計(jì)算機(jī)工程學(xué)院課程設(shè)計(jì)報(bào)告設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 選題名稱： 表達(dá)式求值 姓 名： * 學(xué) 號(hào)： 201412* 專業(yè)班級(jí)： 軟件工程 軟件142 系 （院）： 計(jì)算機(jī)工程學(xué)院 設(shè)計(jì)時(shí)間： 2015.12.212016.1.4 設(shè)計(jì)地點(diǎn)： 計(jì)算機(jī)實(shí)驗(yàn)室、教室 成績：指導(dǎo)教師評(píng)語： 簽名： 年 月 日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 第 22 頁，共 頁1課程設(shè)計(jì)目的1、訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識(shí)，編寫程序求解指定問題。 2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；3、提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)

2、立分析和解決問題的能力；4、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。2課程設(shè)計(jì)任務(wù)與要求：任務(wù)根據(jù)教材數(shù)據(jù)結(jié)構(gòu)-C語言描述（耿國華主編）和參考書數(shù)據(jù)結(jié)構(gòu)題集（C語言版）（嚴(yán)蔚敏、吳偉民主編）選擇課程設(shè)計(jì)題目，要求通過設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用。所選課題：表達(dá)式求值問題描述：一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只

3、含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式結(jié)束符“=”，如：（7+15）*（23-28/4）=。引入表達(dá)式結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。 基本要求：（1） 從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。 （2） 顯示輸入序列和棧的變化過程。要求：1、在處理每個(gè)題目時(shí)，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的分析報(bào)告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī)調(diào)試工作的效率。在程序設(shè)計(jì)階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。 2、設(shè)計(jì)的題目要求達(dá)到一定工作量（

4、300行以上代碼），并具有一定的深度和難度。3、程序設(shè)計(jì)語言推薦使用C/C+，程序書寫規(guī)范，源程序需加必要的注釋;4、每位同學(xué)需提交可獨(dú)立運(yùn)行的程序；5、每位同學(xué)需獨(dú)立提交設(shè)計(jì)報(bào)告書（每人一份），要求編排格式統(tǒng)一、規(guī)范、內(nèi)容充實(shí)，不少于10頁（代碼不算）；6、課程設(shè)計(jì)實(shí)踐作為培養(yǎng)學(xué)生動(dòng)手能力的一種手段，單獨(dú)考核。 3課程設(shè)計(jì)說明書1、 需求分析 功能需求 1.根據(jù)合法的表達(dá)式求出最終結(jié)果。 2.顯示輸入序列和棧的變化過程。 數(shù)據(jù)需求 1、輸入的形式：表達(dá)式=(“=”是表達(dá)式結(jié)束符)； 2、輸入值的范圍：實(shí)數(shù)； 3、輸出的形式：表達(dá)式=結(jié)果； 4、運(yùn)算符 +、-、*、/,； 5、界限符：()、=

5、； 性能需求 在完成題目要求的基礎(chǔ)上，擴(kuò)充操作數(shù)的范圍到實(shí)數(shù)。二、概要設(shè)計(jì)1、數(shù)據(jù)元素由于某些運(yùn)算符可能具有比別的運(yùn)算符更高的優(yōu)先級(jí)，因此表達(dá)式不可能嚴(yán)格按照從左到右的順序進(jìn)行運(yùn)算，這就要求使用棧來執(zhí)行正確的指令。ADT Stack數(shù)據(jù)對(duì)象：D=ai|aiElement，i=1,2,3,，n，n1且n屬于整數(shù)數(shù)據(jù)關(guān)系：R1=|ai-1,aiD，i=2、n；約定an端為棧頂，ai端為棧底2、基本操作及作用(1)初始化棧int InitStack_f(Stack_f *s)/ 初始化數(shù)字棧int InitStack_c(Stack_c *s)/ 初始化運(yùn)算符棧(2)入棧int Push_f(Sta

6、ck_f *s,float e)/數(shù)字入棧int Push_c(Stack_c *s,char e)/運(yùn)算符入棧(3)出棧int Pop(S,x)/ 數(shù)字出棧int charPop(K,x)/ 運(yùn)算符出棧(4)取棧頂元素int GetTop_f(Stack_f *s,float *e)/數(shù)字取棧頂元素int GetTop_c(Stack_c *s,char *e)/運(yùn)算符取棧頂元素(5) 彈出棧頂元素int Pop_f(Stack_f *s,float *e)/彈出棧頂數(shù)字元素，e帶值返回int Pop_c(Stack_c *s,char *e)/彈出棧頂運(yùn)算符元素，e帶值返回3、系統(tǒng)中的子程

7、序和功能說明：/比較運(yùn)算符的優(yōu)先級(jí)int precede(char Top_char,char s1_char);/將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式int Translate(char *s1);/計(jì)算過程int Calculate(Stack_f *s,char *s2);/輸出計(jì)算結(jié)果void result(Stack_f *s,char *str);/判斷等號(hào)是否存在或有誤int Judge(char *s);運(yùn)算符的優(yōu)先級(jí)12+-*/（）=+-*/（=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

8、, , , , , , , , , , !, =; /確定運(yùn)算符的優(yōu)先級(jí)switch(Top_char) / i為下面array的橫標(biāo) case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break;case : i=4;break; case ( : i=5;break; case ) : i=6;break; case = : i=7;break; switch(s1_char)/ j為下面array的縱標(biāo) case + : j=0;break; case - : j=1;break; case

9、* : j=2;break; case / : j=3;break;case : j=4;break; case ( : j=5;break; case ) : j=6;break; case = : j=7;break; 返回優(yōu)先級(jí)比較結(jié)果/中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式/in 中綴表達(dá)式/out 后綴表達(dá)式/return 1轉(zhuǎn)換成功return 0轉(zhuǎn)換失敗int Translate(char *s1) char s280;Stack_c Optr;int i=0,j=0;char t;初始化運(yùn)算符棧Optr;Push_c(&Optr,();while(s1i!=)if(s1i是數(shù)字或小數(shù)點(diǎn)的字

10、符) s2j+=s1i;if(s1i不是數(shù)字或小數(shù)點(diǎn)的字符)s2j+=空格;elseswitch(s1i) case(:將s1i壓入運(yùn)算符站;break; case):彈出運(yùn)算符棧棧頂元素，將該元素賦值給t; break; while(t!=() s2j+=t;彈出運(yùn)算符棧棧頂元素，將該元素賦值給t;break;default:while(取字符站棧頂元素，若優(yōu)先級(jí)大于讀入的運(yùn)算符)彈出棧頂元素并賦值給t;s2j+=t;將t壓入運(yùn)算符棧;i+;彈出棧頂元素并賦值給t;表達(dá)式串已結(jié)束，棧中的運(yùn)算符全部輸出到s2i，并刪除棧頂元素while(t!=() s2j+=t;彈出棧頂元素并賦值給t; 將s

11、2重新賦值給s1；s1i= =;s1i+1=0;return 1;/計(jì)算出最終結(jié)果/in 后綴表達(dá)式/out 運(yùn)算結(jié)果/return 1計(jì)算成功return 0計(jì)算失敗 int Calculate(Stack_f *s,char *s2)float m,x,y,z;int i=0,j=0;while(s2i!=)/ if(若為數(shù)值和小數(shù)點(diǎn))則將其聯(lián)合轉(zhuǎn)換為浮點(diǎn)型后進(jìn)棧；else 彈出數(shù)字棧棧頂元素彈出數(shù)字棧棧頂元素switch(s2i)/讓棧頂和次頂元素與次運(yùn)算符進(jìn)行相應(yīng)的運(yùn)算，運(yùn)算結(jié)果打印并進(jìn)棧case +:z=y+x;輸出y+x=z;break;case -:z=y-x;輸出y-x=z;b

12、reak;case *:z=y*x;輸出y*x=z;break;case /:if(若除數(shù)為零) printf(ERROR !n); return 0; elsez=y/x;輸出y*x=z; break; case :z=pow(y,x);輸出yx=z;break;default: 輸出符號(hào)不合法!; return 0; 將運(yùn)算結(jié)果壓入數(shù)字棧棧頂;i+;return 1;/寫出最終結(jié)果/in中綴表達(dá)式，數(shù)字棧/out中綴表達(dá)式=最終結(jié)果void result(Stack_f *s,char *str) 取數(shù)字棧棧頂；輸出最終結(jié)果；/判斷表達(dá)式的等號(hào)是否合法/in 中綴表達(dá)式int Judge(

13、char *s) If(等號(hào)存在且位置無誤)return 1;elsereturn 0;四、程序設(shè)計(jì)與調(diào)試分析1、 本程序的編寫和調(diào)試環(huán)境為VC+6.0；2、 使用到的頭文件有 #include #include #include #include #include3、 程序所使用的數(shù)據(jù)結(jié)構(gòu)為棧；在該程序中分為浮點(diǎn)型的數(shù)字棧和字符型的運(yùn)算符棧；4、測試用例輸入的表達(dá)式為6*(4.3-0.7)/1.2+3.1(3-1)=：輸出結(jié)果應(yīng)為75.66輸入表達(dá)式15/0=輸出結(jié)果應(yīng)為：ERROR！ERROR！輸入表達(dá)式3-2輸出結(jié)果應(yīng)為：表達(dá)式無結(jié)束符“=”或結(jié)束符位置不合法!輸入表達(dá)式3=2/輸出結(jié)果

14、應(yīng)為：表達(dá)式無結(jié)束符“=”或結(jié)束符位置不合法!5、 用戶手冊(cè)1、 進(jìn)入程序后即顯示提示信息：“請(qǐng)輸入算術(shù)表達(dá)式，以=結(jié)束”以等待用戶輸入待求表達(dá)式，直到輸入“=”為止，如”5*(7.1-8)(4.3+1)/3.1=”該程序僅僅能夠滿足加減乘除和乘方運(yùn)算，若用戶輸入的表達(dá)是不合法，或表達(dá)式包括程序不滿足的運(yùn)算時(shí)，程序報(bào)錯(cuò)或無法運(yùn)行，程序結(jié)束；2、 在用戶正確輸入表達(dá)式后，程序會(huì)自動(dòng)將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式并輸出“轉(zhuǎn)化后的后綴表達(dá)式為：xxxxxxxx”，然后自動(dòng)轉(zhuǎn)換為后綴表達(dá)式，計(jì)算表達(dá)式的值并輸出中間結(jié)果“表達(dá)式=結(jié)果”和最終結(jié)果“The final result is:原表達(dá)式=結(jié)果”；

15、3、 最終結(jié)果輸出后，又有提示信息：“你想繼續(xù)嗎？Y或y為繼續(xù)，其余為退出程序”，以等待用戶輸入是否繼續(xù)運(yùn)行本程序的命令符，若輸入“y”或“Y”，則程序自動(dòng)再次運(yùn)行，重復(fù)2，3步，若輸入其它，程序結(jié)束。4、 本程序只對(duì)實(shí)數(shù)的加減乘除乘方運(yùn)算進(jìn)行求值，且只對(duì)“（）”這種形式的括號(hào)進(jìn)行識(shí)別，“”或“”都不予以識(shí)別，但是”( )”是可以嵌套的，表達(dá)式輸入完后一定要加“=”表示輸入結(jié)束，否則程序出錯(cuò)。6、 測試成果1、操作提示2、 表達(dá)式計(jì)算輸入的表達(dá)式為6*(4.3-0.7)/1.2+3.1(3-1)=3、 表達(dá)式錯(cuò)誤時(shí)輸入表達(dá)式15/0=4. 表達(dá)式包含不合法字符：5. 輸入表達(dá)式無結(jié)束符“=”或

16、結(jié)束符位置不合法(1)表達(dá)式無結(jié)束符“=”(2) 結(jié)束符位置不合法七、源程序清單#include#include#include#include#include#define INIT_SIZE 100 /初始分配最大空間量#define STACKINCREMENT 10 /（默認(rèn)）增補(bǔ)空間量/數(shù)字棧typedef structfloat *base; float *top; int stacksize;Stack_f; /操作符棧typedef structchar *base; char *top; int stacksize; Stack_c;int Judge(char *s);in

17、t InitStack_f(Stack_f *s);int InitStack_c(Stack_c *s);int GetTop_f(Stack_f *s,float *e);int GetTop_c(Stack_c *s,char *e);int Push_f(Stack_f *s,float e);int Push_c(Stack_c *s,char e);int Pop_f(Stack_f *s,float *e);int Pop_c(Stack_c *s,char *e);int precede(char Top_char,char s1_char);int Translate(cha

18、r *s1);int Calculate(Stack_f *s,char *s2);void result(Stack_f *s,char *str);int main()Stack_f stack;char str200;char strk200;char c=Y;while(c=y | c=Y)printf( |-|n);printf( | 表達(dá)式求值 |n);printf( |-程序支持實(shí)數(shù)的加減乘除乘方運(yùn)算-|n); printf( | 請(qǐng)輸入算術(shù)表達(dá)式,以=結(jié)束 |n);printf( |-|n); gets(str);strcpy(strk,str);if(!Judge(str)p

19、rintf(表達(dá)式無結(jié)束符“=”或結(jié)束符位置不合法!n);else if(InitStack_f(&stack)if(Translate(str)printf(轉(zhuǎn)化后的后綴表達(dá)式為：n); puts(str);if(Calculate(&stack,str)result(&stack,strk);elseprintf(ERROR !n);elseprintf(ERROR !n);elseprintf(ERROR !n); printf(你想繼續(xù)嗎？Y或y為繼續(xù)，其余任意鍵退出。n); c=getchar();getchar();/吞噬掉輸入判斷符后的nreturn 0;/構(gòu)造一個(gè)存儲(chǔ)實(shí)型的空棧

20、，預(yù)設(shè)空間為100，分配失敗就退出/return 1:初始化成功 return 0 :初始化失敗int InitStack_f(Stack_f *s)s-base=(float *)malloc(INIT_SIZE*sizeof(float);if(s-base)s-top=s-base;s-stacksize=INIT_SIZE; return 1;else return 0;/構(gòu)造一個(gè)存儲(chǔ)字符型的空棧,預(yù)設(shè)空間為100,分配失敗就退出/return 1:初始化成功 return 0 :初始化失敗int InitStack_c(Stack_c *s)s-base=(char *)malloc

21、(INIT_SIZE*sizeof(char);if(s-base)s-top=s-base;s-stacksize=INIT_SIZE;return 1;else return 0;/若棧s不空，則以e帶值返棧頂元素，否則顯示錯(cuò)誤ERROR,并退出程序/return 1:獲取成功 return 0 :獲取失敗/in Stack_f *s/out float *eint GetTop_f(Stack_f *s,float *e)if(s-top!=s-base)*e=*(s-top-1);return 1;elseprintf(ERROR!);return 0;/取棧頂，若棧s不空，則刪除棧s

22、的棧頂元素，用e帶值返回，否則退出程序/return 1:獲取成功 return 0 :獲取失敗/in Stack_c *s/out char *eint GetTop_c(Stack_c *s,char *e)if(s-top!=s-base)*e=*(s-top-1);return 1;elseprintf(ERROR!n);return 0;/判斷表達(dá)式的等號(hào)是否合法/in 中綴表達(dá)式int Judge(char *s)int len=strlen(s);int j;for(j=0;jtop-s-base=s-stacksize)s-base=(float *)realloc(s-bas

23、e,(s-stacksize+STACKINCREMENT)*sizeof(float);if(!s-base)printf(溢出啦!n);return 0;s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;return 1;/在s的棧頂插入新的棧頂元素e，若棧的當(dāng)前空間已滿，則追加存儲(chǔ)空間/return 1:壓入成功 return 0 :壓入失敗/in char eint Push_c(Stack_c *s,char e)if(s-top-s-base=s-stacksize)s-base=(char *)reall

24、oc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char);if(!s-base)printf(棧滿，溢出n);return 0;s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;return 1;/若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序/return 1:彈出成功 return 0 :彈出失敗/in Stack_f *s/out float *eint Pop_f(Stack_f *s,float *e)if(s-top=s-base)return 0

25、;*e=*-s-top;return 1;/若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序/return 1:彈出成功 return 0 :彈出失敗/in Stack_c *s/out char *eint Pop_c(Stack_c *s,char *e)if(s-top=s-base)return 0;*e=*-s-top;return 1;/比較運(yùn)算符的優(yōu)先級(jí)/in char Top_char,char s1_char/return 1:棧頂運(yùn)算符優(yōu)先級(jí)大于剛讀入的運(yùn)算符；/return 0:棧頂運(yùn)算符優(yōu)先級(jí)小于剛讀入的運(yùn)算符int precede(char Top_cha

26、r,char s1_char)int i=0,j=0; static char array88=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,)return 1;elsereturn 0;/中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式/in 中綴表達(dá)式/out 后綴表達(dá)式/return 1轉(zhuǎn)換成功return 0轉(zhuǎn)換失敗int Translate(char *s1) char s280;Stack_c Optr;int i=0,j=0;char t;InitStack_c(&Opt

27、r);Push_c(&Optr,();while(s1i!=)if(s1i=0 & s1i=9 | s1i=.) s2j+=s1i;if(s1i+19) & s1i+1!=.)s2j+= ;elseswitch(s1i) case(:Push_c(&Optr,s1i);break; case):Pop_c(&Optr,&t); break; while(t!=() s2j+=t;Pop_c(&Optr,&t);break;default:while(GetTop_c(&Optr,&t),precede(t,s1i)Pop_c(&Optr,&t);s2j+=t;Push_c(&Optr,s1i)

28、;i+;Pop_c(&Optr,&t);/表達(dá)式串已結(jié)束，棧中的運(yùn)算符全部輸出到s2i，并刪除棧頂元素while(t!=() s2j+=t;Pop_c(&Optr,&t);for(i=0;i=0 & s2i0) m/=10;j-;i+; Push_f(s,m); GetTop_f(s,&m); printf(get:%gn,m);else Pop_f(s,&x);Pop_f(s,&y);switch(s2i)/讓棧頂和次頂元素與次運(yùn)算符進(jìn)行相應(yīng)的運(yùn)算，運(yùn)算結(jié)果打印并進(jìn)棧case +:z=y+x;printf(%g+%g=%gn,y,x,z);break;case -:z=y-x;printf(

29、%g-%g=%gn,y,x,z);break;case *:z=y*x;printf(%g*%g=%gn,y,x,z);break;case /:if(x=0) printf(ERROR !n); return 0; elsez=y/x;printf(%g/%g=%gn,y,x,z);break; case :z=pow(y,x);printf(%g%g=%gn,y,x,z);break;default:printf(符號(hào)不合法!n); return 0; Push_f(s,z);i+;return 1;/寫出最終結(jié)果/in中綴表達(dá)式，數(shù)字棧/out中綴表達(dá)式=最終結(jié)果void result(

30、Stack_f *s,char *str)float v;GetTop_f(s,&v);printf(The final result is:%s%gn,str,v);4.課程設(shè)計(jì)心得經(jīng)過兩個(gè)禮拜以來的艱辛努力，終于完成了本次課程設(shè)計(jì)的要求。一路走來，程序從一開始的漏洞百出，毫無章法到現(xiàn)在的有板有眼運(yùn)行流暢。我一步步見證著這個(gè)程序的成長，其實(shí)對(duì)我來說，是一個(gè)很焦急到開心的過程。本次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，老師對(duì)完成設(shè)計(jì)的質(zhì)量要求很高，按照軟件開發(fā)的流程來完成這一份課程設(shè)計(jì)，對(duì)于要完成的任務(wù)細(xì)化到了每一天。從需求分析，概要設(shè)計(jì)，詳細(xì)設(shè)計(jì)到后期的程序編碼，并且每一部分任務(wù)在實(shí)驗(yàn)報(bào)告上都有體現(xiàn)，而且，為了能夠?qū)崿F(xiàn)讓使用者輕松使用的效果，也添加了用戶手冊(cè)的部分，而這些恰恰是軟件開發(fā)過程的一個(gè)縮影。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的組合，當(dāng)然也是計(jì)算機(jī)專業(yè)的必修專業(yè)基礎(chǔ)課程。在一開學(xué)的時(shí)候就了解了這門課程的重要性，所以從那時(shí)起我就決定要好好學(xué)習(xí)這門課程，夯實(shí)自己的基礎(chǔ)。在此次課程設(shè)計(jì)中，在一開始選定表達(dá)式求值這個(gè)題目時(shí)，我就了解這是需要運(yùn)用棧的先進(jìn)后出的特