利用栈实现表达式求值

数据结构实践报告学院：计算机科学与技术学院专业：计算机科学与技术班级：1004班学号：1016041910160420姓名：张新凯张磊指导老师：张雪2011年12月3日第-2-页共15页一．题目设计要求利用栈求表达式的值，可供小学生作业，并能给出分数。（限1人完成）要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。二．设计思路与主要算法该题目的核心是利用栈这种数据结构来实现一个加减乘除以及带括弧的混合数学表达式的计算。其次是利用文件来保存和读写试题库、每次做题的成绩和以往成绩的平均值。对于数学表达式的计算，可以设置一个运算符栈和一个数字栈，分别来保存运算符、数字或者中间计算得到的结果。将整个表达式看做一个字符串，从开头依次判断每个字符是运算符还是数字，若是运算符，则根据运算符优先级来确定是将其压栈还是弹栈进行计算；若是数字，则先将其转化并计入一个临时int型变量中，看下一个字符是否为运算符栈，若是，则将临时变量压进数字栈，否则读取下一个数字字符并进行相关处理后累加到临时变量中，直到下一个字符为运算符，将临时变量压进数字栈。最后，当字符为=时，结束计算，得到计算结果。对于试题库，第一次运行程序时需要用户输入若干试题来建立试题库文件，再次运行时磁盘上已经存在试题库文件，故不需再次建立试题库，直接读取文件即可。然后从试题库中通过随机数函数随机抽取若干个试题供用户来做测试。测试过程中可即时跟踪判断用户所给答案是否正确，并给出相关提示。测试完毕后给出本次测试得分，对得分进行评价并将得分存到磁盘文件上。用户可随时查看成绩的历史记录以及其平均成绩，可随时选择退出程序。限于篇幅，具体算法在此不再赘述，可参考下面的源代码清单。三．程序源代码清单：1.//此程序所有文件均保存在了G盘根目录下，实际调试运行时，可根据实际情况更改存2.//储路径3.#includestdio.h4.#includestdlib.h5.#includetime.h6.intN;//定义全局变量，表示试题库试题数量7.typedefstruct8.{9.chara[100];10.intresult;11.}Shiti;//试题数据类型12.typedefstruct13.{14.int*base,*top;15.intsize;16.}Num;//数字栈第-3-页共15页17.typedefstruct18.{19.char*base,*top;20.intsize;21.}Oper;//运算符栈22.intNumInitStack(Num*S1)//构造数字栈23.{24.S1-base=(int*)malloc(100*sizeof(int));25.if(!S1-base)26.{27.printf(申请内存失败!\n);28.return0;29.}30.S1-top=S1-base;31.S1-size=100;32.return1;33.}34.intOperInitStack(Oper*S2)//构造运算符栈35.{36.S2-base=(char*)malloc(100*sizeof(char));37.if(!S2-base)38.{39.printf(申请内存失败!\n);40.return0;41.}42.S2-top=S2-base;43.S2-size=100;44.return1;45.}46.intNumGetTop(Num*S1)//得到数字栈栈顶元素47.{48.inte1;49.if((*S1).top==(*S1).base)50.return0;51.e1=*((*S1).top-1);52.returne1;53.}54.charOperGetTop(Oper*S2)//得到运算符栈栈顶元素55.{56.chare2;第-4-页共15页57.if((*S2).top==(*S2).base)58.return0;59.e2=*((*S2).top-1);60.returne2;61.}62.voidNumPush(Num*S1,inte1)//数字栈压栈63.{64.*(*S1).top++=e1;65.}66.voidOperPush(Oper*S2,chare2)//运算符栈压栈67.{68.*(*S2).top++=e2;69.}70.intNumPop(Num*S1)//数字栈弹栈71.{72.inte1;73.if((*S1).top==(*S1).base)74.return0;75.e1=*--(*S1).top;76.returne1;77.}78.charOperPop(Oper*S2)//运算符栈弹栈79.{80.chare2;81.if((*S2).top==(*S2).base)82.return0;83.e2=*--(*S2).top;84.returne2;85.}86.charPrecede(chara,charb)//判断运算符优先级87.{88.inti,j;89.charTable[8][8]={{'','+','-','*','/','(',')','='},90.{'+','','','','','','',''},91.{'-','','','','','','',''},92.{'*','','','','','','',''},93.{'/','','','','','','',''},94.{'(','','','','','','=',''},95.{')','','','','','','',''},第-5-页共15页96.{'=','','','','','','','='}};//优先级表格97.for(i=0;i8;i++)98.if(Table[0][i]==a)//纵坐标寻找99.break;100.for(j=0;j8;j++)//横坐标寻找101.if(Table[j][0]==b)102.break;103.returnTable[j][i];104.}105.intOperate(inta,chartheta,intb)//计算二元表达式的值106.{107.intc;108.if(theta=='+')109.c=a+b;110.elseif(theta=='-')111.c=a-b;112.elseif(theta=='*')113.c=a*b;114.else115.c=a/b;116.returnc;117.}118.intIsOper(charch)//判断字符ch是否为运算符119.{120.charptr[10]={'+','-','*','/','(',')','='};121.inti;122.for(i=0;i7;i++)123.{124.if(ch==ptr[i])125.return1;126.}127.return0;128.}129.intResult(chara[],Num*num,Oper*oper)//计算表达式的结果130.{131.chartheta;132.intb,d,k=0,i=0,j=0,num2=0;133.NumInitStack(num);//构造数字栈134.OperInitStack(oper);//构造运算符栈135.OperPush(oper,'=');//将“=”压到栈底136.while(a[i]!='='||OperGetTop(oper)!='=')第-6-页共15页137.{138.//对表达式a进行计算139.if(a[i]='0'&&a[i]='9')140.{141.//字符是数字142.k++;143.if(k=j)144.{145.num2=a[i]-48;146.i++;147.}148.if(kj)149.{150.num2=num2*10+(a[i]-48);151.k=j=0;152.i++;153.}154.if(!IsOper(a[i]))155.k++;156.if(k==j)//如果k等于j，说明下一个字符是运算符，即数字字符结束，压进数字栈157.NumPush(num,num2);158.}159.elseif(IsOper(a[i]))160.{161.//字符是运算符162.switch(Precede(a[i],OperGetTop(oper)))163.{164.//该运算符和栈顶运算符进行优先级比较并做相关处理165.case'':166.OperPush(oper,a[i++]);167.if(a[i]!='('&&a[i]!=')')168.j++;169.break;170.case'=':171.OperPop(oper);172.i++;173.break;174.case'':175.theta=OperPop(oper);//运算符栈弹栈176.d=NumPop(num);//数字栈弹栈177.b=NumPop(num);178.NumPush(num,Operate(b,theta,d));//计算结果并压栈179.break;第-7-页共15页180.}181.}182.}183.return(NumGetTop(num));//返回最终计算结果184.}185.intBuildshitiku()//建立试题库186.{187.inti;188.FILE*fp;189.Shitit;190.if(!(fp=fopen(G:\\shitiku.txt,w)))191.{192.printf(无法建立试题库文件！\n);193.return0;194.}195.printf(输入要建立的试题库的试题数目:);196.scanf(%d,&N);197.fprintf(fp,%d\n,N);198.for(i=0;iN;i++)199.{200.printf(输入第%d道题目:\n,i+1);201.scanf(%s,t.a);202.fprintf(fp,%s\n,t.a);//将键盘输入的表达式写进文件203.}204.fclose(fp);205.return1;206.}207.voidXuanti(intn,inta[])//随机选取n个题目，将题号保存在数组a中208.{209.srand((int)time(0));210.inti,j,t;211.a[0]=rand()%N;//产生0-N之间的随机数并记录212.for(i=1;in;i++)213.{214.t=rand()%N;215.for(j=0;ji;j++)216.{217.if(a[j]==t)218.break;219.}220.if(j==i)221.a[i]=t;第-8-页共15页222.else223.i--;224.}225.}226.voidAvescore()//求平均成绩227.{228.FILE*fp1,*fp2;229.intsum=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++;//记录成绩个数240.}241.fclose(fp1);242.a=sum/i;243.if(!(fp2=fopen(G:\\average.txt,w)))244.{245.printf(无法创建或者无法打开平均成绩文件！\n);246.exit(-1);247.}248.fprintf(fp2,%d,a);