1、*大學數據結構課 程 設 計 說 明 書   學生姓名: *學 號： *學 院:*學院專 業: 網絡工程題 目:利用棧求表達式的值成績 指導教師*  2009 年 7 月 9 日1 設計目的數據結構課程設計的目的是，通過設計掌握數據結構課程中學到的基本理論和算法并綜合運用于解決實際問題中，它是理論與實踐相結合的重要過程。設計要求學會如何對實際問題定義相關數據結構，并采用恰當的設計方法和算法解決問題，同時訓練學生進行復雜程序設計的技能和培養良好的程序設計習慣。2 設計內容和要求利用棧求解表達式的值。設計內容

2、：1) 建立試題庫文件，隨機產生n個題目；2) 題目涉及加減乘除，帶括弧的混合運算；3) 利用棧求解表達式的值；4) 隨時可以退出；5) 保留歷史分數，能回顧歷史，給出與歷史分數比較后的評價基本要求：1)系統功能的完善；2)代碼中有必要的注釋3本設計所采用的數據結構棧的數組表示方法（靜態分配整型指針）typedef structtypedef dataMAXSIZE;int top;4功能模塊詳細設計1.功能一：中綴表達式轉化為后綴表達式；2.功能二：后綴表達式求值；3.功能三：文件讀寫；4.功能四：作業評分；5.功能五：歷史成績本次成績比較；6.功能六：輸入“”符號退出程序4.1 詳細設計思

3、想1.首先實現表達式的求值： 要用棧求解一個表達式,就要將這個表達式翻譯成正確求值的一個機器指令序列,即正確解釋表達式,了解算術四則混合運算的規則：(1).先乘除,后加減;(2).從左算到右;(3).先括號內,后括號外再根據這個運算優先的規定來實現對表達式的編譯或解釋執行. 任何一個表達式都是由操作數(st)和操作符(op)組成的，根據四則運算基本法則，在運算的每一步中，任意兩個相繼出現的操作符op1和op2之間的優先關系最多有以下3種：(1).op1的優先級低于op2(2).op1的優先級等于op2(3).op1的優先級小于op2為實現運算符優先，可以使用兩個操作棧，操作棧st,用于存放操作

4、數及運算結果；操作棧op，用于存放操作符。算法思想：(1).首先將中綴表達式轉換成后綴表達式：<1>.從左至右依次掃描中綴表達式的每一個字符，如果是數字字符和“.” ，則直接將它們寫入后綴表達式中。<2>.如果遇到的是開括號“（”，則將它壓入一個操作符棧中，它表明一個新的計算層次的開始，在遇到和它匹配的閉括號時，將棧中元素彈出并放入后綴表達式中，直到棧頂元素為開括號“（”時，將棧頂元素“（”彈出，表明這一層括號內的操作處理完畢。<3>.如果遇到的是操作符，則將該操作符和操作符棧頂元素比較： a)當所遇到的操作符的優先級小于或等于棧頂元素的優先級時，則取出棧頂

5、元素放入后綴表達式，并彈出該棧頂元素，反復執行直到棧頂元素的優先級小于當前操作符的優先級；b)當所遇到的操作符的優先級大于棧頂元素的優先級時，則將它壓入棧中。重復上述步驟直到遇到中綴表達式的結束0，彈出棧中的所有元素并放入后綴表達式中，算法結束。(2).對后綴表達式求值： 將遇到的操作數暫存在一個操作數棧中，凡是遇到操作符，便從棧中彈出兩個操作數執行相應的操作，并將結果存于操作數棧中，直到表達式處理完畢，最后壓入棧中的數就是表達式的結果。2.建立試題庫文件“shitiku.txt”和成績庫文件“chengji.txt”。 試題庫文件“shitiku.txt”中存儲20道帶括號的四則混合運算；成

6、績庫文件“chengji.txt”中存儲歷史成績。3.從試題庫文件“shitiku.txt”中讀出“total”道題： 當做的題目數小于“total”時，用隨機函數產生每次要做的題號。4.對本次作業進行評分： 本次作業共做題“total”道，每道“100/total”分； 做對題目數為“r”,本次作業得分為“r*(100/total)”。5.輸入“”符號時，退出程序。4.2 源代碼#include<stdio.h>#include<stdlib.h>#define MAXSIZE 30int length20=13,15,12,9,11,17,13,15,9,11,11

7、,11,12,10,15,13,18,16,16,9; /*shitiku文件中20個字符串數組的長度*/typedef structfloat dataMAXSIZE;int top;float compvalue(char *postexp) /*后綴表達式求值*/ struct float dataMAXSIZE; int top; st; float a,b,c,d;int k=0; st.top=-1; while(*postexp!='0') switch(*postexp) case '+': a=st.datast.top; st.top-; b

8、=st.datast.top; st.top-; c=b+a; st.top+; st.datast.top=c; break; case '-': a=st.datast.top; st.top-; b=st.datast.top; st.top-; c=b-a; st.top+; st.datast.top=c; break; case '*': a=st.datast.top; st.top-; b=st.datast.top; st.top-; c=b*a; st.top+; st.datast.top=c; break; case '/'

9、;: a=st.datast.top; st.top-; b=st.datast.top; st.top-; if(a!=0) c=b/a; st.top+; st.datast.top=c; else printf("nterror!n"); return(0); break; default: d=0; while(*postexp>='0'&&*postexp<='9') /*讀整數部分*/ d=10*d+*postexp-'0' /*整數部分處理*/ postexp+; if(*postex

10、p='.') /*讀數時遇到小數點*/postexp+;while(*postexp>='0'&&*postexp<='9') /*讀小數部分*/d=d*10+*postexp-'0' postexp+;k+;while(k!=0) /*小數部分處理*/d=d/10.0;k=k-1; st.top+; st.datast.top=d; break; postexp+; return st.datast.top; /*操作棧st中最終剩下表達式運算結果*/void trans(char *exp,char

11、 *postexp) /*將中綴表達式轉換成后綴表達式*/ struct char dataMAXSIZE; int top; op; int i=0; op.top=-1; while(*exp!='0') switch(*exp) case '(': op.top+;op.dataop.top=*exp; exp+;break; case ')': while(op.dataop.top!='(') postexpi+=op.dataop.top; op.top-; op.top-;exp+;break; case '

12、+': case '-': while(op.top!=-1&&op.dataop.top!='(') postexpi+=op.dataop.top; op.top-; op.top+;op.dataop.top=*exp;exp+;break; case '*': case '/': while(op.dataop.top='*'|op.dataop.top='/') postexpi+=op.dataop.top; op.top-; op.top+;op.dataop.

13、top=*exp;exp+;break; case ' ':break; default: while(*exp>='0'&&*exp<='9'|*exp='.') postexpi+=*exp; exp+; postexpi+='#' while(op.top!=-1) postexpi+=op.dataop.top; op.top-; postexpi='0'void main()int i;int n;int t; int former,mark; /*former

14、：歷史成績 mark：本次成績*/char exp30; /*存儲中綴表達式*/float result,answer; /*result：從鍵盤輸入的結果 answer：程序中函數求得的正確答案*/int total,r; /*total：要做的題的總數 r：做對的題目總數*/char postexpMAXSIZE; /*存儲后綴表達式*/char s12030; /*存儲所有的表達式*/FILE *fp;r=0; randomize(); /*產生隨機種子*/fp=fopen("shitiku.txt","r");if(fp=NULL)printf(

15、"file cant open!n");exit (2);for(i=0;i<20;i+)fgets(s1i,30,fp); /*將所有20個表達式存入二維數組s12030中*/fclose(fp);printf("n");printf("input total(0<total<21):");scanf("%d",&total); if(total<0|total>=21) /*total小于0或大于21時，退出*/ exit (0);t=total;while(t>0)

16、 n=random(21);/*產生一個小于21的隨機整數*/for(i=0;i<lengthn;i+)expi=s1ni; /*將第n題存入exp中*/expi='0'printf("nn%s=",exp);scanf("%f",&answer);trans(exp,postexp);result=compvalue(postexp); if(answer='') /*輸入“”即退出*/exit (0); else if(result-answer)<=0.01)/*比較計算結果與正確答案*/ pri

17、ntf("Congratulations! You are right!");r+;elseprintf("The right answer is:%f",result);for(i=0;i<30;i+)expi='0' /*清空用來存放表達式的數組*/t-;mark=r*100/total; /*賦分*/printf("nnYour mark is:%d",mark);fp=fopen("chengji.txt","r"); fscanf(fp,"%d"

18、;,&former); /*讀取文件中存儲的歷史分數*/ fp=fopen("chengji.txt","w");fprintf(fp,"%dn",mark); /*將本次分數存入文件中*/fclose(fp);printf("n");if(mark<=former) /*比較歷史分數與本次分數并給出評價*/printf("ntry hardn");elseprintf("nGreat!");4.3運行結果：.選擇本次要做的題目數：3；每道題為100/3=33分；做對題目，輸出“Congratulations! You are right！”； 做錯題目，輸出“The right an