1、數(shù)據(jù)結(jié)構(gòu)實驗報告一實驗題目表達式求值設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達式求值的過程。測試數(shù)據(jù)：3*（7-2）2*（6+2*（3+6*（6+6）+（6+6）*3+28/（9-9）(一) 需求分析1.本程序需要編寫這樣一個程序：（1）開始（2）首先要建立兩個棧：運算數(shù)棧和運算符棧；（3）向運算符站中存入“n”（也可以是#）這個優(yōu)先級最低的元素；（4）輸入運算表達式；（5）分析數(shù)據(jù)，如果輸入的是運算數(shù)，則儲存，如果輸入的是運算符，則與運算符棧的棧頂元素比較：（1）如果棧頂元素的優(yōu)先級低于當前運算符，則將它讀入運算符棧；（2）在棧頂元素的優(yōu)先級等于當前運算符時，則刪除棧頂元素并返回其值，（這種情

2、況只有輸入結(jié)束或兩個括號相遇時才會出現(xiàn)）分析下一個數(shù)據(jù)運算符；（3）當棧頂元素的優(yōu)先級小于當前運算符時，刪除棧頂元素并返回其值，然后用棧頂元素與其前后的元素進行運算，并將運算后的結(jié)果儲存在運算數(shù)棧中；（6）輸出運算結(jié)果；（7）結(jié)束(二) 概要設(shè)計這個程序的核心是棧的應(yīng)用。1. 基本操作：typedef structchar *base; char *top;int stacksize; SqStack_Symbol;操作結(jié)果：對運算符號棧進行定義；typedef structfloat *base;float *top; /運算數(shù)棧int stacksize;SqStack_Number;操作

3、結(jié)果：對運算數(shù)棧進行定義；void InitStack_Symbol(SqStack_Symbol *S)操作結(jié)果：創(chuàng)建運算符棧；void InitStack_Number(SqStack_Number *S)操作結(jié)果：創(chuàng)建運算數(shù)棧；int GetTop_Symbol(SqStack_Symbol *S) 操作結(jié)果：返回棧頂運算符元素；float GetTop_Number(SqStack_Number *S)操作結(jié)果：返回棧頂運算數(shù)元素；char Push_Symbol(SqStack_Symbol *S,char e)操作結(jié)果：插入棧頂運算符元素；float Push_Number(SqS

4、tack_Number *S,float e)操作結(jié)果：插入棧頂運算數(shù)元素；char Pop_Symbol(SqStack_Symbol *S)操作結(jié)果：刪除棧頂運算數(shù)元素，并返回其值；float Pop_Number(SqStack_Number *S)操作結(jié)果：刪除棧頂運算數(shù)元素，并返回其值；char T8="+-*/()n"操作結(jié)果：定義運算符號；char Prior77 = / 運算符優(yōu)先級表 / '+' '-' '*' '/' '(' ')' 'n' /

5、*'+'*/'>','>','<','<','<','>','>', /*'-'*/'>','>','<','<','<','>','>', /*'*'*/'>','>','>'

6、,'>','<','>','>', /*'/'*/'>','>','>','>','<','>','>', /*'('*/'<','<','<','<','<','=',' ', /*

7、')'*/'>','>','>','>',' ','>','>', /*'n'*/'<','<','<','<','<',' ','=', ;操作結(jié)果：運算符優(yōu)先級比較列表char Precede(char a,char b)操作結(jié)果：判斷運算符優(yōu)先級；float Operat

8、e(float a,char optr,float b)操作結(jié)果：計算兩個操作數(shù)；2.本程序包含五個模塊：主程序，操作數(shù)棧及相關(guān)函數(shù)，操作符棧及相關(guān)函數(shù)，運算符列表及優(yōu)先級表，運算符優(yōu)先級判斷函數(shù)和計算函數(shù)。（三）詳細設(shè)計1.結(jié)構(gòu)體定義typedef structchar *base; /運算符棧char *top;int stacksize;SqStack_Symbol;typedef structfloat *base;float *top; /運算數(shù)棧int stacksize;SqStack_Number;2. 每個模塊的分析：（1）主程序模塊：int main()SqStack_Sy

9、mbol OPTR;SqStack_Number OPND;float a,b,i,m,n;char optr,c,x;InitStack_Symbol(&OPTR); /創(chuàng)操作符棧Push_Symbol(&OPTR,'n'); /以“n”開始InitStack_Number(&OPND); /創(chuàng)建操作數(shù)棧printf("輸入表達式并以'回車'結(jié)尾:n");c=getchar(); if(c=35|(c>=40&&c<=43)|c=45|(c>=47&&c<=57

10、) /輸入數(shù)據(jù)限定為“n”,“+”,“-”,“*”,“/”“()”和“0-9”while(c!='n'|GetTop_Symbol(&OPTR)!='n') /當輸入不是n運算符時 if(c>=48&&c<=57)while(c>=48&&c<=57) i=i*10+(float)c-48;c=getchar(); Push_Number(&OPND,i);elseswitch(Precede(GetTop_Symbol(&OPTR),c) ) /比較優(yōu)先級case'<

11、':Push_Symbol(&OPTR,c); /棧頂元素的優(yōu)先級低，則當前運算符進棧，讀入下一字符c=getchar();break;case'=':x=Pop_Symbol(&OPTR); /棧頂元素與當前運算符優(yōu)先級相等，刪除，并讀入下一字符c=getchar();break;case'>':optr=Pop_Symbol(&OPTR);b=Pop_Number(&OPND); /棧頂元素優(yōu)先級高，運算，結(jié)果進入運算數(shù)棧 a=Pop_Number(&OPND);Push_Number(&OPND

12、,Operate(a,optr,b); break; m=GetTop_Number(&OPND);n=GetTop_Number(&OPND);if(n=int(m)printf("運算結(jié)果：%dn",int(m); /若是整數(shù)，則以整數(shù)輸出else printf("%fn",n);else printf("輸入錯誤!n");return 0;（2）運算符棧及相關(guān)函數(shù)typedef structchar *base; /定義運算符棧char *top;int stacksize;SqStack_Symbol;void

13、 InitStack_Symbol(SqStack_Symbol *S) /創(chuàng)建運算符棧(*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;int GetTop_Symbol(SqStack_Symbol *S) /返回棧頂運算符元素char e;if(*S).top=(*S).base) return ERROR;e= *(*S).top-1);return e;char Pus

14、h_Symbol(SqStack_Symbol *S,char e) /插入棧頂元素if(*S).top-(*S).base>=(*S).stacksize)(*S).base= (char*) realloc (*S).base , (*S).stacksize + STACKINCREMENT)*sizeof(char); /空間不足則增加空間分配if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;c

15、har Pop_Symbol(SqStack_Symbol *S) /刪除棧頂元素char e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;（3）運算數(shù)棧及相關(guān)函數(shù)typedef structfloat *base;float *top; /運算數(shù)棧int stacksize;SqStack_Number;void InitStack_Number(SqStack_Number *S) /創(chuàng)建運算數(shù)棧(*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!(

16、*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;float GetTop_Number(SqStack_Number *S) /返回棧頂運算數(shù)元素 float e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;float Push_Number(SqStack_Number *S,float e) /插入棧頂元素if( (*S).top-(*S).base >= (*S).stacksize) (*S).base=

17、(float*) realloc (*S).base , (*S).stacksize + STACKINCREMENT)*sizeof(float); /空間不足則增加空間分配if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;float Pop_Number(SqStack_Number *S) /刪除棧頂元素，并返回其值float e;if(*S).top=(*S).base) return ERROR;

18、e=*(-(*S).top); return e;（4）運算符表及優(yōu)先級表char T8="+-*/()n"char Prior77 = / 運算符優(yōu)先級表 / '+' '-' '*' '/' '(' ')' 'n' /*'+'*/'>','>','<','<','<','>','>', /*&#

19、39;-'*/'>','>','<','<','<','>','>', /*'*'*/'>','>','>','>','<','>','>', /*'/'*/'>','>','>',&#

20、39;>','<','>','>', /*'('*/'<','<','<','<','<','=',' ', /*')'*/'>','>','>','>',' ','>','>', /*'n

21、'*/'<','<','<','<','<',' ','=',;（5）判斷優(yōu)先級并計算har Precede(char a,char b)int i=0,j=0; /判斷運算符優(yōu)先級while(Ti!=a)i+; while(Tj!=b)j+;return(Priorij); /返回在運算符優(yōu)先級表中的比較結(jié)果float Operate(float a,char optr,float b) /運算函數(shù)float m;switch(optr)cas

22、e'+':m=a+b;break;case'-':m=a-b;break;case'*':m=a*b;break;case'/':if(b!=0) m=a/b;else printf("輸入錯誤!");break;return m;（四）程序使用說明及測試結(jié)果1程序使用說明（1）本程序的運行環(huán)境為VC6.0。（2）進入演示程序后即顯示提示信息：輸入表達式并以回車結(jié)尾：輸入后顯示：運算結(jié)果：2測試結(jié)果輸入表達式：3*（7-2）輸出結(jié)果：15輸入表達式; 2*（6+2*（3+6*（6+6）+（6+6）*3+2輸出結(jié)

23、果：350（五）、實驗總結(jié)(實驗心得)1.你在編程過程中花時多少？答：從周五實驗課到周日晚完成實驗報告，一共用了約八個小時。2.多少時間在紙上設(shè)計？答：兩個小時3.多少時間上機輸入和調(diào)試？答：編程與調(diào)試用的時間最長，大概六個小時。 4.多少時間在思考問題？答：從編程到調(diào)試的八個小時里，面對對我來說困難的程序，和不斷涌現(xiàn)的各種錯誤，我一直在思考怎樣解絕這個問題。5.遇到了哪些難題？你是怎么克服這些困難的？答：在做這項作業(yè)時。我可以說自己遇到了無數(shù)難題，以為我的C語言成績并不好，棧的熟悉度恐怕只有10%。因此完成這項作業(yè)的過程可謂艱辛。首先遇到的困難就是設(shè)計程序。去年C語言學(xué)得很不扎實，

24、我對鏈表的結(jié)構(gòu)都不甚了解，更別說運用與之相關(guān)的算法了。在周五下午數(shù)據(jù)結(jié)構(gòu)的實驗課上，我花了半個小時重新回顧C語言教科書棧上的基礎(chǔ)知識，好在數(shù)據(jù)結(jié)構(gòu)書上有創(chuàng)建棧的程序。由于知識的匱乏，我只能先將書上的棧的定、創(chuàng)建、進棧、出棧函數(shù)敲到電腦上， 然后在紙上設(shè)計相應(yīng)的流程。最后憑借自己腦海里僅存的知識，并利用同學(xué)的幫助，磕磕絆絆地編寫了主函數(shù)。接下來的困難，也就是最大，最麻煩，解決起來最耗費腦力，最枯燥乏味的問題調(diào)試程序。最初的程序編譯之后，問題觸目驚心，我根據(jù)系統(tǒng)的提示，首先補上了缺失的間隔符，又定義了遺漏的變量，再次編譯，錯誤有所減少，但依然多，我又重新修改。接下來的錯誤越來越“高級”，

25、數(shù)據(jù)類型，返回類型，函數(shù)類型等有關(guān)。我便循環(huán)往復(fù)，不厭其煩地修改，每當減少一個錯誤，我都會有幾分高興，而有的時候，修改后會產(chǎn)生更多的錯誤。就這樣一遍又一遍，終于系統(tǒng)顯示沒有錯誤和警告了。我運行了程序。當我按照自己的設(shè)想將輸入數(shù)據(jù)時，敲下回車鍵后結(jié)果卻令我傻了眼。屏幕上沒有任何顯示。，原來許多錯誤是編譯器沒有檢測出來。知道第二天，我參考了網(wǎng)上的一些算法又請教了同學(xué)，才知道自己犯了哪些低級的錯誤。比如說指針的地址和指針所指向的對象的值沒有區(qū)分清楚；函數(shù)的返回值應(yīng)為鏈表的首結(jié)點，而不是函數(shù)中指向該鏈表的指針。后來又經(jīng)過了幾個小時的修改和編譯調(diào)試，我最終才完成了完整地程序。但后來更可怕的事發(fā)生了，我不

26、知怎么竟然丟失了自己編寫的程序！只能憑借記憶重新編寫。知識掌握的不牢固，我又耗費了大量時間，還犯了許多低級錯誤，最終憑借努力終于完成了程序。  6你的收獲有哪些？答：首先，我對棧不分的知識有了更多了解破除了錯誤的認識。其次，通過這次作業(yè)，我掌握了幾種與棧有關(guān)的算法。最后，我還溫習(xí)了有關(guān)C語言的許多知識。 附：完整程序 #include <stdio.h>#include <stdlib.h>#define OK 1 #define ERROR 0#define OVERFLOW 0#define STACK_INIT_SIZE 100#define STACK

27、INCREMENT 10 typedef structchar *base; /運算符棧char *top;int stacksize;SqStack_Symbol;typedef structfloat *base;float *top; /運算數(shù)棧int stacksize;SqStack_Number;void InitStack_Symbol(SqStack_Symbol *S) /創(chuàng)建運算符棧(*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S)

28、.base;(*S).stacksize=STACK_INIT_SIZE;void InitStack_Number(SqStack_Number *S) /創(chuàng)建運算數(shù)棧(*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;int GetTop_Symbol(SqStack_Symbol *S) /返回棧頂運算符元素char e;if(*S).top=(*S).base) ret

29、urn ERROR;e= *(*S).top-1);return e; float GetTop_Number(SqStack_Number *S) /返回棧頂運算數(shù)元素 float e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;char Push_Symbol(SqStack_Symbol *S,char e) /插入棧頂元素if(*S).top-(*S).base>=(*S).stacksize)(*S).base= (char*) realloc (*S).base , (*S).stacksize + S

30、TACKINCREMENT)*sizeof(char); /空間不足則增加空間分配if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;float Push_Number(SqStack_Number *S,float e) /插入棧頂元素if( (*S).top-(*S).base >= (*S).stacksize) (*S).base= (float*) realloc (*S).base , (*S

31、).stacksize + STACKINCREMENT)*sizeof(float); /空間不足則增加空間分配if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;char Pop_Symbol(SqStack_Symbol *S) /刪除棧頂元素char e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;float Pop_Number

32、(SqStack_Number *S) /刪除棧頂元素float e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top); return e;char T8="+-*/()n"char Prior77 = / 運算符優(yōu)先級表 / '+' '-' '*' '/' '(' ')' 'n' /*'+'*/'>','>','<','&l

33、t;','<','>','>', /*'-'*/'>','>','<','<','<','>','>', /*'*'*/'>','>','>','>','<','>','>', /*&#

34、39;/'*/'>','>','>','>','<','>','>', /*'('*/'<','<','<','<','<','=',' ', /*')'*/'>','>','>','>

35、;',' ','>','>', /*'n'*/'<','<','<','<','<',' ','=' ; char Precede(char a,char b)int i=0,j=0; /判斷運算符優(yōu)先級while(Ti!=a)i+; while(Tj!=b)j+;return(Priorij); /返回在運算符優(yōu)先級表中的比較結(jié)果float Operate(float a,char optr,float b) /運算函數(shù)float m;switch(optr)case'+':m=a+b;break;case'-':m=a-b;break;ca