利用棧實現(xiàn)表達式求值

1、利用棧實現(xiàn)表達式求值數(shù)據(jù)結(jié)構(gòu)實踐報告 學(xué) 院：計算機科學(xué)與技術(shù)學(xué)院 專 業(yè)：計算機科學(xué)與技術(shù) 班 級：1004班 學(xué) 號： 姓 名：張新凱 張 磊 指導(dǎo)老師：張 雪 2011年12月3日一題目設(shè)計要求利用棧求表達式的值，可供小學(xué)生作業(yè)，并能給出分數(shù)。（限1 人完成）要求：建立試題庫文件，隨機產(chǎn)生n個題目；題目涉及加減乘除，帶括弧的混合運算；隨時可以退出；保留歷史分數(shù)，能回顧歷史，給出與歷史分數(shù)比較后的評價。2 設(shè)計思路與主要算法該題目的核心是利用棧這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)一個加減乘除以及帶括弧的混合數(shù)學(xué)表達式的計算。其次是利用文件來保存和讀寫試題庫、每次做題的成績和以往成績的平均值。對于數(shù)學(xué)表達式的

2、計算，可以設(shè)置一個運算符棧和一個數(shù)字棧，分別來保存運算符、數(shù)字或者中間計算得到的結(jié)果。將整個表達式看做一個字符串，從開頭依次判斷每個字符是運算符還是數(shù)字，若是運算符，則根據(jù)運算符優(yōu)先級來確定是將其壓棧還是彈棧進行計算；若是數(shù)字，則先將其轉(zhuǎn)化并計入一個臨時int型變量中，看下一個字符是否為運算符棧，若是，則將臨時變量壓進數(shù)字棧，否則讀取下一個數(shù)字字符并進行相關(guān)處理后累加到臨時變量中，直到下一個字符為運算符，將臨時變量壓進數(shù)字棧。最后，當字符為"="時，結(jié)束計算，得到計算結(jié)果。對于試題庫，第一次運行程序時需要用戶輸入若干試題來建立試題庫文件，再次運行時磁盤上已經(jīng)存在試題庫文件，

3、故不需再次建立試題庫，直接讀取文件即可。然后從試題庫中通過隨機數(shù)函數(shù)隨機抽取若干個試題供用戶來做測試。測試過程中可即時跟蹤判斷用戶所給答案是否正確，并給出相關(guān)提示。測試完畢后給出本次測試得分，對得分進行評價并將得分存到磁盤文件上。用戶可隨時查看成績的歷史記錄以及其平均成績，可隨時選擇退出程序。限于篇幅，具體算法在此不再贅述，可參考下面的源代碼清單。三程序源代碼清單：1. op=(*s1).base)2. return 0;3. e1=*(*s1).top-1);4. return e1;5. 6. char opergettop(oper *s2) op=(*s2).base)7. retur

4、n 0;8. e2=*(*s2).top-1);9. return e2;10. 11. void numpush(num *s1,int e1) op+=e1;12. 13. void operpush(oper *s2,char e2) op+=e2;14. 15. int numpop(num *s1) op=(*s1).base)16. return 0;17. e1=*-(*s1).top;18. return e1;19. 20. char operpop(oper *s2) op=(*s2).base)21. return 0;22. e2=*-(*s2).top;23. ret

5、urn e2;24. 25. char precede(char a,char b) ;26. scanf("%d",&r);27. if(ati.result=r)28. 29. k+;30. printf("答案正確！n");31. 32. else33. 34. printf("答案錯誤！正確答案為：%dn",ati.result);35. 36. 37. score=100*k/n;38. printf("n本次得分：%dn",score); 題n");39. printf("t

6、t 2.查看歷史成績n");40. printf("tt 3.退出系統(tǒng)nn");41. printf("tt*n");42. printf("tt請選擇：");43. scanf("%d",&a);44. while(a<1|a>3);45. return a;46. 47. int main()48. 49. file *fp;50. int i;51. char c;52. shiti s1000;53. num num;54. oper oper;55. if(!(fp=fope

7、n("g:","r") ;56. si.result=result(si.a,&num,&oper);57. 58. fclose(fp);59. while(1)60. 61. switch(menu()62. 63. case 1:64. do65. 66. zuoti(s);67. printf("n是否繼續(xù)做題？y-是，n-否：");68. getchar();69. scanf("%c",&c);70. while(c!='n'&&c!='n

8、');71. break;72. case 2:73. history(); /輸出成績74. system("pause");75. break;76. case 3:77. printf("nt歡迎使用，再見！nnt");78. system("pause");79. exit (0); /退出系統(tǒng)80. 81. 82. return 0;83. 4 運行結(jié)果及分析首次運行程序時如圖1。圖1按任意鍵以建立試題庫，如圖2。圖2依次輸入所要建立的試題數(shù)目n和n個表達式，現(xiàn)以輸入十個為例，實際可多輸入一些，如圖3。圖3再次按任意

9、鍵即可進入系統(tǒng)正常進行作業(yè)使用，見圖4，另外，從第二次使用本系統(tǒng)開始，每次剛打開后的界面也為圖4。圖4之后輸入1即可做題，根據(jù)提示輸入要做多少題n，然后屏幕上會依次出現(xiàn)n道題，等待用戶給出結(jié)果。用戶輸入結(jié)果后即時給出判定，對答錯的題給出正確答案，之后給出這次做題所得分數(shù)（百分制），并給出與以往成績的比較（第一次由于之前不存在成績記錄，于是與自己相比），見圖5。圖5選擇是否繼續(xù)做題，這里選擇“是”，再做一組題，輸入"y"，見圖7（下頁）?？梢钥闯鲞@一次比上次進步了。輸入"n"，結(jié)束做題，返回圖4所示界面。輸入2查看成績歷史記錄，見圖6。 圖6按任意鍵后返回圖4界面，輸入3退出系統(tǒng)，見圖8。圖7 圖8按任意鍵后即推出系統(tǒng)。以后再運行該程序時，將從圖4界面開始。參考文獻1 嚴蔚敏，吳為民編