1、word可編輯 數據結構與數據庫 實驗報告實驗題目算術表達式求值學院：化學與材料科學學院專業班級：09級材料科學與工程系 PB0920603姓名：維谷學號：PB09206285 郵箱：指導教師：賈伯琪實驗時間：2022年10月10日一、 需要分析問題描述：表達式計算是實現程序設計語言的根本問題之一，它的實現是棧的應用的一個典型例子。設計一個程序，演示通過將數學表達式字符串轉化為后綴表達式，并通過后綴表達式結合棧的應用實現對算術表達式進行四那么混合運算。問題分析：在計算機中，算術表達式由常量、變量、運算符和括號組成。由于不同的運算符具有不同的優先級，又要考慮括號，因此，算術表達式的求值不可能嚴格

2、地從左到右進行。因而在程序設計時，借助棧實現。設置運算符棧字符型和運算數棧浮點型輔助分析算符優先關系。在讀入表達式的字符序列的同時完成運算符和運算數的識別處理，然后進行運算數的數值轉換在進行四那么運算。在運算之后輸出正確運算結果，輸入表達式后演示在求值中運算數棧的棧頂數據變化過程，最后得到運算結果。算法規定：輸入形式：一個算術表達式，由常量、變量、運算符和括號組成以字符串形式輸入。為使實驗更完善，允許操作數為實數，操作符為、.表示小數點、+、-、*、/、表示乘方，用#表示結束。輸出形式：演示表達式運算的中間結果和整個表達式的最終結果，以浮點型輸出。程序功能：對實數的加減乘除乘方運算能正確的運算

3、出結果，并能正確對錯誤輸入和無定義的運算報錯，能連續測試多組數據。測試數據：正確輸入：12*3.6/3+42-1# 輸出結果：194.4 無定義運算：12*3.6/22-4+1# 輸出結果：表達式出錯，除數為0，無意義 錯誤輸入：12+s# 輸出結果：ERROR！二、 概要設計擬采用兩種類型的展分別對操作數和操作符進行操作。程序中將涉及以下兩個抽象數據類型：1、設定“操作數的棧的抽象數據類型定義：ADT SqStack_f數據對象：D=數據關系：R1=<>|,i=2,，n約定端為棧頂，端為棧底。根本操作： InitStack_f(&S) 操作結果：構造一個空棧S。 GetT

4、op_f(&S,&e) 初始條件：棧S已存在。 操作結果：用e返回S的棧頂元素。 Push_f(&S，ch) 初始條件：棧S已存在。 操作結果：插入元素ch為新的棧頂元素。 Pop_f(&S,&e) 初始條件：棧S已存在。 操作結果：刪除S的棧頂元素，并以e返回其值。ADT SqStack_f2、設定“操作符的棧的抽象數據類型定義：ADT SqStack_c數據對象：D=數據關系：R1=<>|,i=2,，n約定端為棧頂，端為棧底。根本操作： InitStack_c(&S) 操作結果：構造一個空棧S。 GetTop_c(&S,&

5、amp;e) 初始條件：棧S已存在。 操作結果：用e返回S的棧頂元素。 Push_c(&S，ch) 初始條件：棧S已存在。 操作結果：插入元素ch為新的棧頂元素。 Pop_c(&S,&e) 初始條件：棧S已存在。 操作結果：刪除S的棧頂元素，并以e返回其值。ADT SqStack_c3、本程序包含六個模塊1主程序模塊void main( )初始化；while(命令=“繼續)接受數據；處理數據；接受命令；2棧模塊實現棧抽象數據類型3判斷運算符優先級模塊判斷運算符的優先級別4后綴表達式轉換模塊將中綴表達式轉換為后綴表達式，方便操作5無括號表示式求值運算模塊根據后綴表達式求值

6、，并輸出中間和最終結果6運算結果輸出模塊以正確形式輸出表達式的值三、 詳細設計1、主程序中需要的全程量#define TTACK_INIT_SIZE 100 /初始分配最大空間量#define STACKINCREMENT 10 /默認增補空間量2、結點類型、指針類型typedef structfloat *base; /存儲實型數據元素的一位數組float *top; /棧頂指針int stacksize; /棧數組容量SqStack_f; /有序存儲實型的順序表類型typedef structchar *base; /存儲字符數據元素的一位數組char *top; /棧頂指針int sta

7、cksize; /棧數組容量SqStack_c; /有序存儲字符型的順序表類型void InitStack_f(SqStack_f *s)void InitStack_f(SqStack_f *s)/構造一個存儲實型字符型的空棧，預設空間為100，分配失敗就退出void GetTop_f(SqStack_f *s,float *e)void GetTop_c(SqStack_c *s,char *e)/假設棧s不空，那么以e帶值返棧頂元素，否那么顯示錯誤“ERROR,并退出程序void Push_f(SqStack_f *s,float e)void Push_c(SqStack_c *s,c

8、har e)/在s的棧頂插入新的棧頂元素e，假設棧的當前空間已滿，那么追加存儲空間void Pop_f(SqStack_f *s,float *e)void Pop_c(SqStack_c *s,char *e)/假設棧s不空，那么刪除棧s的棧頂元素，用e帶值返回，否那么退出程序其中局部操作的偽碼算法由于比擬類似，以浮點型的棧為例void InitStack_f(SqStack_f *s)/構造一個存儲實型的空棧，預設空間為100，分配失敗就退出s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float);if(!s->base)exi

9、t(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;void GetTop_f(SqStack_f *s,float *e)/假設棧s不空，那么以e帶值返棧頂元素，否那么顯示錯誤“ERROR,并退出程序if(s->top=s->base)printf("ERROR!n");exit(1);*e=*(s->top-1);void Push_f(SqStack_f *s,float e)/在s的棧頂插入新的棧頂元素e，假設棧的當前空間已滿，那么追加存儲空間if(s->top-s->ba

10、se>=s->stacksize)s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float);if(!s->base)printf("OVERFLOW!n");exit(1);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;void Pop_f(SqStack_f *s,float *e)/假設棧s不空，那么刪除棧s的棧頂元素，用

11、e帶值返回，否那么退出程序if(s->top=s->base)exit(1);*e=*-s->top;3、判斷運算符優先級的算法：算符間的優先關系如下：+-*/()#+>=<<<<>>->>=<<<>>*>>>=><>>/>>>>=<>>(<<<<<=)>>>>>>#<<<<<=偽碼算法：int precede(ch

12、ar Top_char,char s1_char)/棧頂的運算符賦給Top_char，新讀入的運算符賦給s1_char。判斷它們的優先級 /假設棧頂運算符優先級高，那么返回1，否那么返回0int i,pre2;char op2;op0=Top_char; /棧頂的運算符賦給op0op1=s1_char; /新讀入的運算符賦給op1for(i=0;i<2;i+)switch(opi)case'(':case')':prei=0;break; /將括號的優先級設為0case'+':case'-':prei=1;break; /將

13、+ - 運算符的優先級設為1case'*':case'/':prei=2;break; /將* / 運算符的優先級設為2case'':prei=3;break; /將 運算符的優先級設為3if(pre0>=pre1) /棧頂元素優先級高返回1return 1;elsereturn 0; /否那么返回04、中綴表達式轉換為后綴表達式的算法：算法過程描述：1) 首先將左括號“(壓進棧，作為棧底元素；2) 從左而右對算數表達式進行掃描，每次讀入一個字符s1i；3) 假設遇到數字或小數點，那么立即寫入s2i，假設遇算數運算符，將“ 空格寫入s2i；

14、4) 遇到左括號“(那么壓棧；5) 假設遇算術運算符，如果它們的優先級比棧頂元素高，那么直接進棧，否那么彈出棧頂元素輸出到s2i，直到新棧頂元素的優先級比它低，然后將它壓棧；6) 假設遇到右括號“，那么將棧頂元素輸出到s2i，直到棧頂元素為“，然后相互抵消；7) 當掃描到“#符號，說明表達式串已全部輸入，將棧中的運算符全部輸出到s2i，并刪除棧頂元素。偽碼算法：void Translate(char *s1) /中綴表達式轉換為后綴表達式char s280;SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);/初始化一個存儲字符型的

15、空棧，便于存儲運算符Push_c(&Optr,'(');/ 首先將左括號“(壓進棧，作為棧底元素while(s1i!='#') /當掃描到的不是“#，即表達式串沒結束時if(s1i>='0' && s1i<='9' | s1i='.') /假設果是數字或小數點那么將其輸出給s2is2j+=s1i;if(s1i+1<'0' | s1i+1>'9') && s1i+1!='.')s2j+=' '

16、;elseswitch(s1i) /掃描到的是運算符 case'(':Push_c(&Optr,s1i);break;/ 遇到左括號“(那么壓棧case')':Pop_c(&Optr,&t); /假設遇到右括號“，那么將棧頂元素輸出到s2iwhile(t!='(') /直到棧頂元素為“，然后相互抵消s2j+=t;Pop_c(&Optr,&t);break;default:while(GetTop_c(&Optr,&t),precede(t,s1i)/遇到算數運算符那么比擬優先級Pop_c(&

17、amp;Optr,&t);/棧頂元素優先級高，那么彈出到s2is2j+=t;Push_c(&Optr,s1i);/棧頂元素優先級低，直接壓棧i+;Pop_c(&Optr,&t);while(t!='(') /表達式串已結束，棧中的運算符全部輸出到s2i，并刪除棧頂元素s2j+=t;Pop_c(&Optr,&t);for(i=0;i<j;i+) /將s2復制給s1s1i=s2i; s1i= '#'s1i+1='0'/為了方便打印后綴表達式，在字符串結尾加05、表示式求值運算的算法：算法描述：1）

18、 讀入無括號的后綴表達式；2） 假設為數值和小數點那么將其聯合轉換為浮點型后進棧存放操作數；3） 假設為運算符，讓棧頂元素和次頂元素與次運算符進行相應的運算，運算結果打印并進棧；4） 重復23步驟，直到輸入為“#，那么此時棧中的結果便是所追求的表達式的值。數值轉換為實數的算法描述：1） 假設為數字，那么將其減去'0'的ASCII碼后就得到該數的數值，并暫存于一個變量m上；2） 假設繼續為數字，也將其減去'0'的ASCII碼后就得到該數的數值，并將其值加上已存的m*10后的值再存于m；3） 重復2步驟直到遇到小數點，從小數點后的數開始，在重復2步驟的通知，也記下小

19、數點后的位數n；4） 當遇到“ 空格后，即表示此輪需轉換的數已讀入完畢，那么將m除以10的你次方，那么此時的之記為轉換后的實數。偽碼算法：void Calculate(SqStack_f *s,char *s2)float m,x,y,z;int i=0,j=0;while(s2i!='#')/讀入后綴表達式直到“#符號為止if(s2i>='0' && s2i<='9' | s2i='.') / 假設為數值和小數點/那么將其聯合轉換為浮點型后進棧/數值轉換為實數m=0;while(s2i!='

20、' && 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("The result is:%gn&quo

21、t;,m);else /讀入的為運算符Pop_f(s,&x);/彈出棧頂元素Pop_f(s,&y);/彈出次頂元素switch(s2i)/讓棧頂和次頂元素與次運算符進行相應的運算，運算結果打印并進棧case '+':z=y+x;printf("The result is:%gn",z);break;case '-':z=y-x;printf("The result is:%gn",z);break;case '*':z=y*x;printf("The result is:%gn&q

22、uot;,z);break;case '/':if(x=0) /報錯功能 printf("表達式出錯，除數為0，無意義n"); exit(1); elsez=y/x;printf("The result is:%gn",z);break;case '':z=1;for(j=1;j<=x;j+) /乘方的運算 z=z*y; printf("The result is:%gn",z); Push_f(s,z);i+;6、結果輸出的偽碼算法：void result(SqStack_f *s)float

23、v;GetTop_f(s,&v);printf("The final result is:%gn",v);/以適宜的形式輸出結果，省去不必要的小數點7、主程序的偽碼算法：void main()SqStack_f stack;char str80,c='Y'while(c='y' | c='Y')/判斷是否繼續本程序printf("請輸入算術表達式本程序支持實數的加減乘除乘方運算，結束前請輸入#號！n"); gets(str);/輸入表達式 InitStack_f(&stack);/初始化一個

24、存儲運算結果實型的棧 Translate(str);/調用“中綴表達式轉換為后綴表達式函數 printf("轉化后的后綴表達式為：n");/檢驗后綴表達式是否轉換正確 puts(str);/輸出后綴表達式 Calculate(&stack,str);/計算無括號表達式的值 result(&stack);/調用“結果輸出函數 printf("你想繼續嗎？'Y'或'y'為繼續，其余為退出程序n");/增加程序的連續輸入功能 c=getchar();getchar();/吞噬掉輸入判斷符后的n8、函數的調用關系圖

25、mainTranslateCalculateresultprecede四、 調試分析1、 在編程過程中，為了增加程序的實用性，將程序適用圍擴大到了實數型，并增加了連續輸入功能；2、 在編程過程中，為了增加程序的健壯性，在運算除法時，考慮到除數為“0時的報錯和及時退出；3、 在調試過程中，最初一下子出來程序就出錯，為了方便檢查錯誤，故在主函數中增加了檢查后綴表達式是否轉換正確的函數，并在每一步計算都跟蹤結果是否正確；4、 從程序實驗題的編制過程中容易看出，線性表的廣泛應用，特別是順序存儲結構的棧的應用。此題中涉及兩元素類型字符型和浮點型的棧，由于是面向過程的語言，故只能分別定義。五、 用戶使用說

26、明1、 本程序的運行環境為Windows7旗艦版操作系統，執行文件為：算術表達式求值.exe；2、 進入程序后即顯示提示信息：“請輸入算術表達式本程序支持實數的加減乘除乘方運算，結束前請輸入#號！以等待用戶輸入待求表達式，直到輸入“#為止，假設用戶輸入的表達式為一個空字符串，那么顯示ERROR，程序結束；3、 在用戶正確輸入表達式后，程序會自動將其轉換為后綴表達式并輸出“轉化后的后綴表達式為：xxxxxxxx，然后自動計算表達式的值并輸出中間結果“The result is：xxxxx和最終結果“The final result is:xxxx；4、 最終結果輸出后，又有提示信息：“你想繼續嗎

27、？'Y'或'y'為繼續，其余為退出程序，以等待用戶輸入是否繼續運行本程序的命令符，假設輸入“y或“Y，那么程序自動再次運行，重復2，3步，假設輸入其它，程序結束。5、 本程序只對實數的加減乘除乘方運算進行求值，且只對“這種形式的括號進行識別，“或“都不予以識別，表達式輸入完后一定要加“#表示輸入結束。六、 測試結果1、 正確輸入：12*3.6/3+42-1#2、 無定義運算：12*3.6/(22-4)+1#運行界面：3、 錯誤輸入：12+s#運行界面：以上結果與自己在進行程序概要分析時的余項結果一致七、 心得體會這次實驗設計讓我更加了解并更加靈活運用大一學到的C

28、程序設計和這個學期學到的數據結構。實驗任務要求不僅要求對課本知識有較深刻的了解，同時要求程序設計者有較強的思維和動手能力和更加了解編程思想和編程技巧。這次實驗設計讓我有一個深刻的體會，那就是細節決定成敗，編程最需要的是嚴謹，如何的嚴謹都不過分，往往檢查了半天發現錯誤發生在某個括號，分號，引號，或者數據類型上，或者將“i打成“1。就像我在寫Calculate函數時，在進行數值轉換時，一個“放錯了位置，讓我糾結了很久。在寫Translate函數時，switchs1i寫成switchs11，很仔細的檢查，花了一個多小時才發現次錯誤。 程序設計時，也不要怕遇到錯誤，在實際操作過程中犯的一些錯誤還會有意

29、外的收獲，感覺課程設計很有意思。在具體操作中這學期所學的數據結構的理論知識得到穩固，到達課程設計的根本目的，也發現自己的缺乏之出，在以后的上機中應更加注意，同時體會到C語言具有的語句簡潔，使用靈活，執行效率高等特點。發現上機的重要作用，特別算術表達式有了深刻的理解。最后，感老師在這次課程設計的悉心指導，祝老師身體健康，工作順利。參考文獻：1. 數據結構(C語言版) 嚴蔚敏 清華大學 2. C程序設計 譚浩強 清華大學 3. 數據結構題集C語言版 嚴蔚敏 吳偉民 米寧 清華大學 4. C程序設計學習指導與練習 賈伯琪 中國科學技術大學八、 附錄“表達式求值源程序代碼：#include<st

30、dio.h>#include<stdlib.h>#include<malloc.h>#define TTACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structfloat *base;float *top;int stacksize;SqStack_f;typedef structchar *base;char *top;int stacksize;SqStack_c;void InitStack_f(SqStack_f *s)s->base=(float *)malloc(TTACK_INIT_SIZ

31、E*sizeof(float);if(!s->base)exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;void InitStack_c(SqStack_c *s)s->base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char);if(!s->base)exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;void GetTop_f(SqStack_f *s,float *e)if(s->to

32、p=s->base)printf("ERROR!n");exit(1);*e=*(s->top-1);void GetTop_c(SqStack_c *s,char *e)if(s->top=s->base)printf("ERROR!n");exit(1);*e=*(s->top-1);void Push_f(SqStack_f *s,float e)if(s->top-s->base>=s->stacksize)s->base=(float *)realloc(s->base,(s-&

33、gt;stacksize+STACKINCREMENT)*sizeof(float);if(!s->base)printf("OVERFLOW!n");exit(1);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;void Push_c(SqStack_c *s,char e)if(s->top-s->base>=s->stacksize)s->base=(char *)realloc(s->base,(s->

34、;stacksize+STACKINCREMENT)*sizeof(char);if(!s->base)printf("OVERFLOW!n");exit(1);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;void Pop_f(SqStack_f *s,float *e)if(s->top=s->base)exit(1);*e=*-s->top;void Pop_c(SqStack_c *s,char *e)if(s->to

35、p=s->base)exit(1);*e=*-s->top;int precede(char Top_char,char s1_char)int i,pre2;char op2;op0=Top_char;op1=s1_char;for(i=0;i<2;i+)switch(opi)case'(':case')':prei=0;break;case'+':case'-':prei=1;break;case'*':case'/':prei=2;break;case'':p

36、rei=3;break;if(pre0>=pre1)return 1;elsereturn 0;void Translate(char *s1)char s280;SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);Push_c(&Optr,'(');while(s1i!='#')if(s1i>='0' && s1i<='9' | s1i='.')s2j+=s1i;if(s1i+1<'0'

37、| s1i+1>'9') && s1i+1!='.')s2j+=' 'elseswitch(s1i)case'(':Push_c(&Optr,s1i);break;case')':Pop_c(&Optr,&t);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);while(t!='(')s2j+=t;Pop_c(&Optr,&t);for(i=0;i<j;i+)s1i=s2i;s1i='#'s1i+1='0'void Calculate(SqStack_f *s,char *s2)float m,x,y,z;int i=0,j=0;while(s2i!='#')if(s2i>='0' && s2