淮海工學院數據結構課程設計表達式求值(可浮點型,指數運算)

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

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

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

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

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

6、棧int Push_f(Stack_f *s,float e)/數字入棧int Push_c(Stack_c *s,char e)/運算符入棧(3)出棧int Pop(S,x)/ 數字出棧int charPop(K,x)/ 運算符出棧(4)取棧頂元素int GetTop_f(Stack_f *s,float *e)/數字取棧頂元素int GetTop_c(Stack_c *s,char *e)/運算符取棧頂元素(5) 彈出棧頂元素int Pop_f(Stack_f *s,float *e)/彈出棧頂數字元素，e帶值返回int Pop_c(Stack_c *s,char *e)/彈出棧頂運算符元

7、素，e帶值返回3、系統(tǒng)中的子程序和功能說明：/比較運算符的優(yōu)先級int precede(char Top_char,char s1_char);/將中綴表達式轉化為后綴表達式int Translate(char *s1);/計算過程int Calculate(Stack_f *s,char *s2);/輸出計算結果void result(Stack_f *s,char *str);/判斷等號是否存在或有誤int Judge(char *s);運算符的優(yōu)先級12+-*/（）=+>><<<<>>->><<<<>

8、;>*>>>><<>>/>>>><<>>>>>>><>>（<<<<<<=）>>>><>>=<<<<<<= 計算中綴表達式的值初始運算符棧 后綴表達式初始數字棧 轉化為后綴表達式取數字棧頂主程序模塊彈出運算符棧 表達式運算符 數字壓入數字棧運算符數字彈出數字棧 壓入運算符棧棧數字取運算符棧頂 運算符 運算符壓入運算符棧運算符 計算結果輸

9、出結果 SC圖三、詳細設計1、 基本參數類型的設計 （1）/* 定義運算符類型棧 */typedef structchar *base; /存儲字符數據元素的一維數組char *top; /棧頂指針int stacksize; /棧數組容量Stack_c; /有序存儲字符型的順序表類型/* 定義整型棧 */ /* 定義運算數字類型棧 */typedef structfloat *base; /存儲實型數據元素的一維數組float *top; /棧頂指針int stacksize; /棧數組容量Stack_f; /有序存儲實型的順序表類型2/構造一個存儲實型的空棧，預設空間為100，分配失敗就退

10、出/return 1:初始化成功 return 0 :初始化失敗 int InitStack_f(Stack_f *s);分配指定的空間;if(分配成功)初始化棧頂元素；初始化棧的容量; return 1;else return 0;/構造一個存儲字符型的空棧,預設空間為100,分配失敗就退出/return 1:初始化成功 return 0 :初始化失敗int InitStack_c(Stack_c *s)分配指定的空間;if(分配成功)初始化棧頂元素；初始化棧的容量; return 1;else return 0;/若棧s不空，則以e帶值返棧頂元素，否則顯示錯誤"ERROR&quo

11、t;,并退出程序/return 1:獲取成功 return 0 :獲取失敗/in Stack_f *s/out float *eint GetTop_f(Stack_f *s,float *e)if(棧不為空)*e=棧頂元素;return 1;else報錯;return 0;/取棧頂，若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序/in Stack_c *s/out char *e/return 1:獲取成功 return 0 :獲取失敗int GetTop_f(Stack_f *s,char *e)if(棧不為空)*e=棧頂元素;return 1;else報錯;return 0

12、;/在s的棧頂插入新的棧頂元素e，若棧的當前空間已滿，則追加存儲空間/in float e/return 1:壓入成功 return 0 :壓入失敗int Push_f(Stack_f *s,float e)if(棧滿)增加數字棧的儲存空間;if(增加失敗)printf("棧滿，溢出n");return 0;重置棧頂指針;重置棧的容量;壓入元素;return 1;/在s的棧頂插入新的棧頂元素e，若棧的當前空間已滿，則追加存儲空間/in char e/return 1:壓入成功 return 0 :壓入失敗int Push_c(Stack_c *s,char e)if(棧滿)

13、增加運算符棧的儲存空間;if(增加失敗)printf("棧滿，溢出n");return 0;重置棧頂指針;重置棧的容量;壓入元素;return 1;/若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序/in Stack_f *s/out float *e/return 1:彈出成功 return 0 :彈出失敗int Pop_f(Stack_f *s,float *e)if(棧為空)return 0;*e=棧頂元素;return 1;/若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序/in Stack_c *s/out char *e/return 1

14、:彈出成功 return 0 :彈出失敗int Pop_c(Stack_c *s,char *e)if(棧為空)return 0;*e=棧頂元素;return 1;/比較運算符的優(yōu)先級/in char Top_char,char s1_char/return 1:棧頂運算符優(yōu)先級大于剛讀入的運算符；/return 0:棧頂運算符優(yōu)先級小于剛讀入的運算符int precede( char Top_char,char s1_char)int i=0,j=0; /儲存各個運算符優(yōu)先級的比較結果static char array88='>', '>', &#

15、39;<', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<'

16、,'<', '>', '>', '>', '>', '>', '>', '<','<', '>', '>','>', '>', '>', '>', '<','<', '>', '>'

17、,'<', '<', '<', '<', '<','<', '=', '!', '>', '>', '>', '>', '<','!', '>', '>', '<', '<', '<', '&

18、lt;', '<','<', '!', '=' /確定運算符的優(yōu)先級switch(Top_char) / i為下面array的橫標 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 ')

19、9; : i=6;break; case '=' : i=7;break; switch(s1_char)/ j為下面array的縱標 case '+' : j=0;break; case '-' : j=1;break; case '*' : j=2;break; case '/' : j=3;break;case '' : j=4;break; case '(' : j=5;break; case ')' : j=6;break; case '='

20、 : j=7;break; 返回優(yōu)先級比較結果/中綴表達式轉換為后綴表達式/in 中綴表達式/out 后綴表達式/return 1轉換成功return 0轉換失敗int Translate(char *s1) char s280;Stack_c Optr;int i=0,j=0;char t;初始化運算符棧Optr;Push_c(&Optr,'(');while(s1i!='=')if(s1i是數字或小數點的字符) s2j+=s1i;if(s1i不是數字或小數點的字符)s2j+=空格;elseswitch(s1i) case'(':將s1

21、i壓入運算符站;break; case')':彈出運算符棧棧頂元素，將該元素賦值給t; break; while(t!='(') s2j+=t;彈出運算符棧棧頂元素，將該元素賦值給t;break;default:while(取字符站棧頂元素，若優(yōu)先級大于讀入的運算符)彈出棧頂元素并賦值給t;s2j+=t;將t壓入運算符棧;i+;彈出棧頂元素并賦值給t;表達式串已結束，棧中的運算符全部輸出到s2i，并刪除棧頂元素while(t!='(') s2j+=t;彈出棧頂元素并賦值給t; 將s2重新賦值給s1；s1i= '='s1i+1=&#

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

23、:z=y-x;輸出y-x=z;break;case '*':z=y*x;輸出y*x=z;break;case '/':if(若除數為零) printf("ERROR !n"); return 0; elsez=y/x;輸出y*x=z; break; case '':z=pow(y,x);輸出yx=z;break;default: 輸出符號不合法!; return 0; 將運算結果壓入數字棧棧頂;i+;return 1;/寫出最終結果/in中綴表達式，數字棧/out中綴表達式=最終結果void result(Stack_f *s

24、,char *str) 取數字棧棧頂；輸出最終結果；/判斷表達式的等號是否合法/in 中綴表達式int Judge(char *s) If(等號存在且位置無誤)return 1;elsereturn 0;四、程序設計與調試分析1、 本程序的編寫和調試環(huán)境為VC+6.0；2、 使用到的頭文件有 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> #include<math.h>3、 程序所使用的數據結構為棧；在該程序中分為浮點型的數字棧和字

25、符型的運算符棧；4、測試用例輸入的表達式為6*(4.3-0.7)/1.2+3.1(3-1)=：輸出結果應為75.66輸入表達式15/0=輸出結果應為：ERROR！ERROR！輸入表達式3-2輸出結果應為：表達式無結束符“=”或結束符位置不合法!輸入表達式3=2/輸出結果應為：表達式無結束符“=”或結束符位置不合法!5、 用戶手冊1、 進入程序后即顯示提示信息：“請輸入算術表達式，以=結束”以等待用戶輸入待求表達式，直到輸入“=”為止，如”5*(7.1-8)(4.3+1)/3.1=”該程序僅僅能夠滿足加減乘除和乘方運算，若用戶輸入的表達是不合法，或表達式包括程序不滿足的運算時，程序報錯或無法運行

26、，程序結束；2、 在用戶正確輸入表達式后，程序會自動將中綴表達式轉換為后綴表達式并輸出“轉化后的后綴表達式為：xxxxxxxx”，然后自動轉換為后綴表達式，計算表達式的值并輸出中間結果“表達式=結果”和最終結果“The final result is:原表達式=結果”；3、 最終結果輸出后，又有提示信息：“你想繼續(xù)嗎？'Y'或'y'為繼續(xù)，其余為退出程序”，以等待用戶輸入是否繼續(xù)運行本程序的命令符，若輸入“y”或“Y”，則程序自動再次運行，重復2，3步，若輸入其它，程序結束。4、 本程序只對實數的加減乘除乘方運算進行求值，且只對“（）”這種形式的括號進行識別，“

27、”或“”都不予以識別，但是”( )”是可以嵌套的，表達式輸入完后一定要加“=”表示輸入結束，否則程序出錯。6、 測試成果1、操作提示2、 表達式計算輸入的表達式為6*(4.3-0.7)/1.2+3.1(3-1)=3、 表達式錯誤時輸入表達式15/0=4. 表達式包含不合法字符：5. 輸入表達式無結束符“=”或結束符位置不合法(1)表達式無結束符“=”(2) 結束符位置不合法七、源程序清單#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include&l

28、t;math.h>#define INIT_SIZE 100 /初始分配最大空間量#define STACKINCREMENT 10 /（默認）增補空間量/數字棧typedef structfloat *base; float *top; int stacksize;Stack_f; /操作符棧typedef structchar *base; char *top; int stacksize; Stack_c;int Judge(char *s);int InitStack_f(Stack_f *s);int InitStack_c(Stack_c *s);int GetTop_f(S

29、tack_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(char *s1);int Calculate(Stack_f *s,char *s2);void result(Stack_f *s,cha

30、r *str);int main()Stack_f stack;char str200;char strk200;char c='Y'while(c='y' | c='Y')printf(" |-|n");printf(" | 表達式求值 |n");printf(" |-程序支持實數的加減乘除乘方運算-|n"); printf(" | 請輸入算術表達式,以'='結束 |n");printf(" |-|n"); gets(str);s

31、trcpy(strk,str);if(!Judge(str)printf("表達式無結束符“=”或結束符位置不合法!n");else if(InitStack_f(&stack)if(Translate(str)printf("轉化后的后綴表達式為：n"); puts(str);if(Calculate(&stack,str)result(&stack,strk);elseprintf("ERROR !n");elseprintf("ERROR !n");elseprintf("E

32、RROR !n"); printf("你想繼續(xù)嗎？'Y'或'y'為繼續(xù)，其余任意鍵退出。n"); c=getchar();getchar();/吞噬掉輸入判斷符后的'n'return 0;/構造一個存儲實型的空棧，預設空間為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->

33、;base;s->stacksize=INIT_SIZE; return 1;else return 0;/構造一個存儲字符型的空棧,預設空間為100,分配失敗就退出/return 1:初始化成功 return 0 :初始化失敗int InitStack_c(Stack_c *s)s->base=(char *)malloc(INIT_SIZE*sizeof(char);if(s->base)s->top=s->base;s->stacksize=INIT_SIZE;return 1;else return 0;/若棧s不空，則以e帶值返棧頂元素，否則顯示錯

34、誤"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的棧頂元素，用e帶值返回，否則退出程序/return 1:獲取成功 return 0 :獲取失敗/in Stack_c *s/out char *eint G

35、etTop_c(Stack_c *s,char *e)if(s->top!=s->base)*e=*(s->top-1);return 1;elseprintf("ERROR!n");return 0;/判斷表達式的等號是否合法/in 中綴表達式int Judge(char *s)int len=strlen(s);int j;for(j=0;j<len-1;j+)if(sj='=')return 0;else if(slen-1='=')return 1;elsereturn 0;/在s的棧頂插入新的棧頂元素e，若棧

36、的當前空間已滿，則追加存儲空間/return 1:壓入成功 return 0 :壓入失敗/in float eint Push_f(Stack_f *s,float e)if(s->top-s->base>=s->stacksize)s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float);if(!s->base)printf("溢出啦!n");return 0;s->top=s->base+s->stacksiz

37、e;s->stacksize+=STACKINCREMENT;*s->top+=e;return 1;/在s的棧頂插入新的棧頂元素e，若棧的當前空間已滿，則追加存儲空間/return 1:壓入成功 return 0 :壓入失敗/in char eint Push_c(Stack_c *s,char e)if(s->top-s->base>=s->stacksize)s->base=(char *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char);if(!s->base

38、)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;*e=*-s->top;return

39、 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ōu)先級/in char Top_char,char s1_char/return 1:棧頂運算符優(yōu)先級大于剛讀入的運算符；/return 0:棧頂運算符優(yōu)先級小于剛讀入的運算符int precede(char Top_char,char

40、 s1_char)int i=0,j=0; static char array88='>', '>', '<', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '<', '>', '>', &#

41、39;>', '>', '>', '>', '<','<', '>', '>', '>', '>', '>', '>', '<','<', '>', '>','>', '>', '>', &

42、#39;>', '<','<', '>', '>','<', '<', '<', '<', '<','<', '=', '!', '>', '>', '>', '>', '<','!', '>&

43、#39;, '>', '<', '<', '<', '<', '<','<', '!', '=' switch(Top_char) / i為下面array的橫標 case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break; case '/' : i=3;break;case &#

44、39;' : i=4;break; case '(' : i=5;break; case ')' : i=6;break; case '=' : i=7;break; switch(s1_char)/ j為下面array的縱標 case '+' : j=0;break; case '-' : j=1;break; case '*' : j=2;break; case '/' : j=3;break;case '' : j=4;break; case '

45、(' : j=5;break; case ')' : j=6;break; case '=' : j=7;break; if(arrayij='>')return 1;elsereturn 0;/中綴表達式轉換為后綴表達式/in 中綴表達式/out 后綴表達式/return 1轉換成功return 0轉換失敗int Translate(char *s1) char s280;Stack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);Push_c(&Optr,'(&#

46、39;);while(s1i!='=')if(s1i>='0' && s1i<='9' | s1i='.') s2j+=s1i;if(s1i+1<'0' | s1i+1>'9') && s1i+1!='.')s2j+=' 'elseswitch(s1i) case'(':Push_c(&Optr,s1i);break; case')':Pop_c(&Optr,&am

47、p;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);i+;Pop_c(&Optr,&t);/表達式串已結束，棧中的運算符全部輸出到s2i，并刪除棧頂元素while(t!='(') s2j+=t;Pop_c(&Optr,&t);for(i=0;i

48、<j;i+) s1i=s2i; s1i= '='s1i+1='0'return 1;/計算/in 后綴表達式/out 運算結果/return 1計算成功return 0計算失敗int Calculate(Stack_f *s,char *s2)float m,x,y,z;int i=0,j=0;while(s2i!='=')/ 若為數值和小數點，則將其聯(lián)合轉換為浮點型后進棧 if(s2i>='0' && s2i<='9' | s2i='.')m=0;while(s2

49、i!=' ' && s2i!='.')m=m*10+(float)(s2i+-'0');if(s2i='.')j=0;i+;while(s2i!=' ')m=m*10+(float)(s2i+-'0'); j+; while(j>0) 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

50、)/讓棧頂和次頂元素與次運算符進行相應的運算，運算結果打印并進棧case '+':z=y+x;printf("%g+%g=%gn",y,x,z);break;case '-':z=y-x;printf("%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