數(shù)據(jù)結構實驗二——算術表達式求值實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結構與數(shù)據(jù)庫實驗報告實驗題目算術表達式求值學院：化學與材料科學學院專業(yè)班級：09級材料科學與工程系 PB姓名：李維谷學號：PB 郵箱：liwg指導教師：賈伯琪實驗時間：2010年10月10日一、 需要分析問題描述：表達式計算是實現(xiàn)程序設計語言的基本問題之一，它的實現(xiàn)是棧的應用的一個典型例子。設計一個程序，演示通過將數(shù)學表達式字符串轉(zhuǎn)化為后綴表達式，并通過后綴表達式結合棧的應用實現(xiàn)對算術表達式進行四則混合運算。問題分析：在計算機中，算術表達式由常量、變量、運算符和括號組成。由于不同的運算符具有不同的優(yōu)先級，又要考慮括號，因此，算術表達式的求值不可能嚴格地從左到右進行

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

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

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

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

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

7、組char *top; /棧頂指針int stacksize; /棧數(shù)組容量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)vo

8、id Push_c(SqStack_c *s,char 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(floa

9、t);if(!s->base)exit(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

10、->top-s->base>=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

11、不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序if(s->top=s->base)exit(1);*e=*-s->top;3、判斷運算符優(yōu)先級的算法：算符間的優(yōu)先關系如下：+-*/()#+>=<<<<>>->>=<<<>>*>>>=><>>/>>>>=<>>(<<<<<=)>>>>>>#<<<<<=偽碼算法：

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

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

14、”（空格）寫入s2i；4) 遇到左括號“(”則壓棧；5) 若遇算術運算符，如果它們的優(yōu)先級比棧頂元素高，則直接進棧，否則彈出棧頂元素輸出到s2i，直到新棧頂元素的優(yōu)先級比它低，然后將它壓棧；6) 若遇到右括號“）”，則將棧頂元素輸出到s2i，直到棧頂元素為“（”，然后相互抵消；7) 當掃描到“#”符號，表明表達式串已全部輸入，將棧中的運算符全部輸出到s2i，并刪除棧頂元素。偽碼算法：void Translate(char *s1) /中綴表達式轉(zhuǎn)換為后綴表達式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='.') /若果是數(shù)字或小數(shù)點則將其輸出給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)/遇到算數(shù)運算符則

17、比較優(yōu)先級Pop_c(&Optr,&t);/棧頂元素優(yōu)先級高，則彈出到s2is2j+=t;Push_c(&Optr,s1i);/棧頂元素優(yōu)先級低，直接壓棧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、表示式求值運算

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

19、）步驟的通知，也記下小數(shù)點后的位數(shù)n；4） 當遇到“ ”（空格）后，即表示此輪需轉(zhuǎn)換的數(shù)已讀入完畢，則將m除以10的你次方，則此時的之記為轉(zhuǎn)換后的實數(shù)。偽碼算法：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='.') / 若為數(shù)值和小數(shù)點/則將其聯(lián)合轉(zhuǎn)換為浮點型后進棧/數(shù)值轉(zhuǎn)換為實數(shù)m=0;while(

20、s2i!=' ' && s2i!='.') /讀入的只為數(shù)字m=m*10+(float)(s2i+-'0');/轉(zhuǎn)換為十進制的整數(shù)if(s2i='.')/遇到小數(shù)點后j=0;i+;while(s2i!=' ')m=m*10+(float)(s2i+-'0');/轉(zhuǎn)換為十進制的整數(shù) j+; /記錄小數(shù)點后的位數(shù)while(j>0) /轉(zhuǎn)換為實數(shù)m/=10;j-;i+; Push_f(s,m); GetTop_f(s,&m); printf("The result

21、 is:%gn",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 resu

22、lt is:%gn",z);break;case '/':if(x=0) /報錯功能 printf("表達式出錯，除數(shù)為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_

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

24、ack);/初始化一個存儲運算結果（實型）的棧 Translate(str);/調(diào)用“中綴表達式轉(zhuǎn)換為后綴表達式函數(shù)” printf("轉(zhuǎn)化后的后綴表達式為：n");/檢驗后綴表達式是否轉(zhuǎn)換正確 puts(str);/輸出后綴表達式 Calculate(&stack,str);/計算無括號表達式的值 result(&stack);/調(diào)用“結果輸出函數(shù)” printf("你想繼續(xù)嗎？'Y'或'y'為繼續(xù)，其余為退出程序n");/增加程序的連續(xù)輸入功能 c=getchar();getchar();/吞噬掉輸入判

25、斷符后的n8、函數(shù)的調(diào)用關系圖mainTranslateCalculateresultprecede四、 調(diào)試分析1、 在編程過程中，為了增加程序的實用性，將程序適用范圍擴大到了實數(shù)型，并增加了連續(xù)輸入功能；2、 在編程過程中，為了增加程序的健壯性，在運算除法時，考慮到除數(shù)為“0”時的報錯和及時退出；3、 在調(diào)試過程中，最初一下子出來程序就出錯，為了方便檢查錯誤，故在主函數(shù)中增加了檢查后綴表達式是否轉(zhuǎn)換正確的函數(shù)，并在每一步計算都跟蹤結果是否正確；4、 從程序?qū)嶒烆}的編制過程中容易看出，線性表的廣泛應用，特別是順序存儲結構的棧的應用。本題中涉及兩元素類型（字符型和浮點型）的棧，由于是面向過程的

26、語言，故只能分別定義。五、 用戶使用說明1、 本程序的運行環(huán)境為Windows7旗艦版操作系統(tǒng)，執(zhí)行文件為：算術表達式求值.exe；2、 進入程序后即顯示提示信息：“請輸入算術表達式本程序支持實數(shù)的加減乘除乘方運算，結束前請輸入#號！”以等待用戶輸入待求表達式，直到輸入“#”為止，若用戶輸入的表達式為一個空字符串，則顯示ERROR，程序結束；3、 在用戶正確輸入表達式后，程序會自動將其轉(zhuǎn)換為后綴表達式并輸出“轉(zhuǎn)化后的后綴表達式為：xxxxxxxx”，然后自動計算表達式的值并輸出中間結果“The result is：xxxxx”和最終結果“The final result is:xxxx”；4、

27、 最終結果輸出后，又有提示信息：“你想繼續(xù)嗎？'Y'或'y'為繼續(xù)，其余為退出程序”，以等待用戶輸入是否繼續(xù)運行本程序的命令符，若輸入“y”或“Y”，則程序自動再次運行，重復2，3步，若輸入其它，程序結束。5、 本程序只對實數(shù)的加減乘除乘方運算進行求值，且只對“（）”這種形式的括號進行識別，“”或“”都不予以識別，表達式輸入完后一定要加“#”表示輸入結束。六、 測試結果1、 正確輸入：12*（3.6/3+42-1）#2、 無定義運算：12*（3.6/(22-4)+1）#運行界面：3、 錯誤輸入：12+s#運行界面：以上結果與自己在進行程序概要分析時的余項結果一致

28、七、 心得體會這次實驗設計讓我更加了解并更加靈活運用大一學到的C程序設計和這個學期學到的數(shù)據(jù)結構。實驗任務要求不僅要求對課本知識有較深刻的了解，同時要求程序設計者有較強的思維和動手能力和更加了解編程思想和編程技巧。這次實驗設計讓我有一個深刻的體會，那就是細節(jié)決定成敗，編程最需要的是嚴謹，如何的嚴謹都不過分，往往檢查了半天發(fā)現(xiàn)錯誤發(fā)生在某個括號，分號，引號，或者數(shù)據(jù)類型上，或者將“i”打成“1”。就像我在寫Calculate（）函數(shù)時，在進行數(shù)值轉(zhuǎn)換時，一個“”放錯了位置，讓我糾結了很久。在寫Translate（）函數(shù)時，switch（s1i）寫成switch（s11），很仔細的檢查，花了一個多

29、小時才發(fā)現(xiàn)次錯誤。 程序設計時，也不要怕遇到錯誤，在實際操作過程中犯的一些錯誤還會有意外的收獲，感覺課程設計很有意思。在具體操作中這學期所學的數(shù)據(jù)結構的理論知識得到鞏固，達到課程設計的基本目的，也發(fā)現(xiàn)自己的不足之出，在以后的上機中應更加注意，同時體會到C語言具有的語句簡潔，使用靈活，執(zhí)行效率高等特點。發(fā)現(xiàn)上機的重要作用，特別算術表達式有了深刻的理解。最后，感謝老師在這次課程設計的悉心指導，祝老師身體健康，工作順利。參考文獻：1.數(shù)據(jù)結構(C語言版) 嚴蔚敏 清華大學出版社 2.C程序設計 譚浩強 清華大學出版社 3.數(shù)據(jù)結構題集（C語言版）嚴蔚敏 吳偉民 米寧 清華大學出版社 4.C程序設計學

30、習指導與練習賈伯琪 中國科學技術大學出版社八、 附錄“表達式求值”源程序代碼：#include<stdio.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(S

31、qStack_f *s)s->base=(float *)malloc(TTACK_INIT_SIZE*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

32、_SIZE;void GetTop_f(SqStack_f *s,float *e)if(s->top=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->

33、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 Push_c(SqStack_c *s,char e)if(s->top-s->base>=s->s

34、tacksize)s->base=(char *)realloc(s->base,(s->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=*-

35、s->top;void Pop_c(SqStack_c *s,char *e)if(s->top=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'

36、;*':case'/':prei=2;break;case'':prei=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'

37、; | 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,&t);while(t!='(')s2j+=t;Pop_c(&Optr,&t);break;default:while(GetTop

38、_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' && s2i