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

1、數(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é)表達式的計算，可以設(shè)置一個運

2、算符棧和一個數(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. /此程序所有文件均保存在了G盤根目錄下，實際調(diào)試運行時，可根據(jù)實際情況更改存2. /儲路徑3. #include 4. #include 5. #include 6. int N; /定義全局變量，表示試題庫試題數(shù)量7. typedef struct8. 9. char

4、 a100;10. int result;11. Shiti; /試題數(shù)據(jù)類型12. typedef struct13. 14. int *base,*top;15. int size;16. Num; /數(shù)字棧17. typedef struct18. 19. char *base,*top;20. int size;21. Oper; /運算符棧22. int NumInitStack(Num *S1) /構(gòu)造數(shù)字棧23. 24. S1-base=(int *)malloc(100*sizeof(int);25. if(!S1-base)26. 27. printf(申請內(nèi)存失敗!n);2

5、8. return 0;29. 30. S1-top=S1-base;31. S1-size=100;32. return 1;33. 34. int OperInitStack(Oper *S2) /構(gòu)造運算符棧35. 36. S2-base=(char *)malloc(100*sizeof(char);37. if(!S2-base)38. 39. printf(申請內(nèi)存失敗!n);40. return 0;41. 42. S2-top=S2-base;43. S2-size=100;44. return 1;45. 46. int NumGetTop(Num *S1) /得到數(shù)字棧棧頂

6、元素47. 48. int e1;49. if(*S1).top=(*S1).base)50. return 0;51. e1=*(*S1).top-1);52. return e1;53. 54. char OperGetTop(Oper *S2) /得到運算符棧棧頂元素55. 56. char e2;57. if(*S2).top=(*S2).base)58. return 0;59. e2=*(*S2).top-1);60. return e2;61. 62. void NumPush(Num *S1,int e1) /數(shù)字棧壓棧63. 64. *(*S1).top+=e1;65. 66

7、. void OperPush(Oper *S2,char e2) /運算符棧壓棧67. 68. *(*S2).top+=e2;69. 70. int NumPop(Num *S1) /數(shù)字棧彈棧71. 72. int e1;73. if(*S1).top=(*S1).base)74. return 0;75. e1=*-(*S1).top;76. return e1;77. 78. char OperPop(Oper *S2) /運算符棧彈棧79. 80. char e2;81. if(*S2).top=(*S2).base)82. return 0;83. e2=*-(*S2).top;8

8、4. return e2;85. 86. char Precede(char a,char b) /判斷運算符優(yōu)先級87. 88. int i,j;89. char Table88= ,+,-,*,/,(,),=,90. +,91. -,92. *,93. /,94. (, ,96. =, ,=; /優(yōu)先級表格97. for(i=0;i8;i+)98. if(Table0i=a) /縱坐標尋找99. break;100. for(j=0;j8;j+) /橫坐標尋找101. if(Tablej0=b)102. break;103. return Tableji;104. 105. int Ope

9、rate(int a,char theta,int b) /計算二元表達式的值106. 107. int c;108. if(theta=+)109. c=a+b;110. else if(theta=-)111. c=a-b;112. else if(theta=*)113. c=a*b;114. else115. c=a/b;116. return c;117. 118. int IsOper(char ch) /判斷字符ch是否為運算符119. 120. char ptr10=+,-,*,/,(,),=;121. int i;122. for(i=0;i=0&ai=9)140. 141.

10、 /字符是數(shù)字142. k+;143. if(kj)149. 150. num2=num2*10+(ai-48);151. k=j=0;152. i+;153. 154. if(!IsOper(ai)155. k+;156. if(k=j) /如果k等于j，說明下一個字符是運算符，即數(shù)字字符結(jié)束，壓進數(shù)字棧157. NumPush(num,num2);158. 159. else if(IsOper(ai)160. 161. /字符是運算符162. switch(Precede(ai,OperGetTop(oper)163. 164. /該運算符和棧頂運算符進行優(yōu)先級比較并做相關(guān)處理165.

11、case :175. theta=OperPop(oper); /運算符棧彈棧176. d=NumPop(num); /數(shù)字棧彈棧177. b=NumPop(num);178. NumPush(num,Operate(b,theta,d); /計算結(jié)果并壓棧179. break;180. 181. 182. 183. return (NumGetTop(num); /返回最終計算結(jié)果184. 185. int Buildshitiku() /建立試題庫186. 187. int i;188. FILE *fp;189. Shiti t;190. if(!(fp=fopen(G:shitiku.

12、txt,w)191. 192. printf(無法建立試題庫文件！n);193. return 0;194. 195. printf(輸入要建立的試題庫的試題數(shù)目: );196. scanf(%d,&N);197. fprintf(fp,%dn,N);198. for(i=0;iN;i+)199. 200. printf(輸入第%d道題目:n,i+1);201. scanf(%s,t.a);202. fprintf(fp,%sn,t.a); /將鍵盤輸入的表達式寫進文件203. 204. fclose(fp);205. return 1;206. 207. void Xuanti(int n,

13、int a) /隨機選取n個題目，將題號保存在數(shù)組a中208. 209. srand(int)time(0);210. int i,j,t;211. a0=rand()%N; /產(chǎn)生0-N之間的隨機數(shù)并記錄212. for(i=1;in;i+)213. 214. t=rand()%N;215. for(j=0;ji;j+)216. 217. if(aj=t)218. break;219. 220. if(j=i)221. ai=t;222. else223. i-;224. 225. 226. void Avescore() /求平均成績227. 228. FILE *fp1,*fp2;229

14、. int sum=0,i=0,s,a;230. if(!(fp1=fopen(G:score.txt,r)231. 232. printf(無法打開成績信息文件！n);233. exit (-1);234. 235. while(!feof(fp1) /讀出所有的歷史成績并求和236. 237. fscanf(fp1,%d,&s);238. sum+=s;239. i+; /記錄成績個數(shù)240. 241. fclose(fp1);242. a=sum/i;243. if(!(fp2=fopen(G:average.txt,w)244. 245. printf(無法創(chuàng)建或者無法打開平均成績文件

15、！n);246. exit (-1);247. 248. fprintf(fp2,%d,a); /將平均值寫入文件中249. fclose(fp2);250. 251. void Zuoti(Shiti a) /做題252. 253. system(cls);254. printf(tt*好好學(xué)習(xí)天天向上*nn);255. int n,i,r,k=0,score,ave;256. FILE *fp,*fp1;257. printf(請輸入要做幾道題：);258. scanf(%d,&n);259. int tn; /在VC+6.0編譯環(huán)境下該條語句編譯通不過，可改為定義一個足夠大的數(shù)組，例如i

16、nt t100;260. Xuanti(n,t); /調(diào)用Xuanti函數(shù)從試題庫中隨機抽取n道題目261. for(i=0;i=90)280. printf(優(yōu)秀，繼續(xù)保持！n);281. else if(score=80)282. printf(良好，還需努力！n);283. else if(score=70)284. printf(一般，繼續(xù)加油！n);285. else if(score=60)286. printf(及格，多多努力！n);287. else288. printf(糟糕，不及格，該好好學(xué)習(xí)了！n);289. if(!(fp=fopen(G:score.txt,a)290

17、. 291. printf(無法建立或者無法打開成績信息文件！n);292. exit (-1);293. 294. fprintf(fp, %d,score); /將本次成績寫入文件295. fclose(fp);296. Avescore();297. if(!(fp1=fopen(G:average.txt,r)298. 299. printf(無法創(chuàng)建或者無法打開平均成績文件！n);300. exit (-1);301. 302. fscanf(fp1,%d,&ave); /讀出之前成績的平均成績303. if(scoreave)304. printf(n成績較以前相比有所進步，繼續(xù)努

18、力！n);305. else if(scoreave)306. printf(n成績較以前相比退步了，要多多練習(xí)，不要氣餒！n);307. else308. printf(n成績與以前持平n);309. 310. void History() /輸出歷史成績311. 312. FILE *fp,*fp1;313. int s,a;314. if(!(fp=fopen(G:score.txt,r)315. 316. printf(無法打開成績信息文件！n);317. exit (-1);318. 319. printf(歷史成績顯示如下：n);320. while(!feof(fp)321. 3

19、22. fscanf(fp,%d,&s);323. printf(%d ,s);324. 325. fclose(fp);326. printf(n);327. if(!(fp1=fopen(G:average.txt,r)328. 329. printf(無法打開平均成績文件！n);330. exit (-1);331. 332. fscanf(fp1,%d,&a);333. printf(平均為：%dnn,a);334. 335. int menu() /菜單函數(shù)336. 337. int a;338. do339. 340. system(cls);341. printf(tt*好好學(xué)習(xí)

20、天天向上*nn);342. printf(tt 1.做題n);343. printf(tt 2.查看歷史成績n);344. printf(tt 3.退出系統(tǒng)nn);345. printf(tt*n);346. printf(tt請選擇：);347. scanf(%d,&a);348. while(a3);349. return a;350. 351. int main()352. 353. FILE *fp;354. int i;355. char c;356. Shiti s1000;357. Num num;358. Oper oper;359. if(!(fp=fopen(G:shiti

21、ku.txt,r) /如果試題庫文件不存在，則建立試題庫360. 361. printf(t*歡迎使用*nn);362. printf(t程序第一次運行，尚無試題庫，請先建立試題庫！nnt);363. system(pause);364. if(Buildshitiku()365. printf(成功建立試題庫！n);366. system(pause);367. fp=fopen(G:shitiku.txt,r);368. 369. fscanf(fp,%d,&N); /將試題庫文件中的信息讀到內(nèi)存中370. for(i=0;iN;i+)371. 372. fscanf(fp,%s,si.a);373. si.result=Result(si.a,&num,&oper);374. 375. fclose(fp);376. while(1)377. 378. switch(menu()379. 380. case 1:381. do382. 383. Zuoti(s);384. printf(n是否繼續(xù)做題？y-是，n-否：);385. getchar();386. scanf(%c,&c);387. while(c!=n&c!=N);388. break;