C语言上机实验报告书 表达式求值实验报告

一．需求分析设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。（1）输入的形式：表达式，例如2*(3+4)包含的运算符只能有'+'、'-'、'*'、'/'、'('、')'；（2）输出的形式：运算结果，例如2*(3+4)=14；（3）程序所能达到的功能：对表达式求值并输出二．系统设计1．栈的抽象数据类型定义：ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…,n}约定an端为栈顶，ai端为栈底基本操作：Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值}ADTStack2．主程序的流程：EvaluateExpression()函数实现了对表达式求值的功能，main()函数直接调用EvaluateExpression()对输入的表达式求值输出函数的调用关系图：mainPushprecedeInPopReturnOpOrd3．各个模块的主要功能：*Push(SC*s,charc)：把字符压栈*Push(SF*s,floatf)：把数值压栈*Pop(SC*s)：把字符退栈*Pop(SF*s)：把数值退栈Operate(a,theta,b)：根据theta对a和b进行'+'、'-'、'*'、'/'、'^'操作In(Test,*TestOp)：若Test为运算符则返回true，否则返回falseReturnOpOrd(op,*TestOp)：若Test为运算符，则返回此运算符在数组中的下标precede(Aop,Bop)：根据运算符优先级表返回Aop与Bop之间的优先级EvaluateExpression(*MyExpression)：用算符优先法对算术表达式求值三．调试分析（1）刚开始只编写了一个Push和一个Pop函数，但因为在EvacuateExpression()里既有运算符入/出栈，又有运算数入/出栈，运行下来总是出错。所以就编写了两个不同的Push和Pop函数，分别使用。四．测试结果输入表达式：2+3*4/5-1输入表达式：5*(10-2*3)-8EvaluateExpressionOperate输出输入表达式：(5-17)/3+2五．用户手册输入语法正确的、不含变量的数学表达式（运算符只能是'+'、'-'、'*'、'/'、'('、')'），回车即输出结果。六．附录源程序：#includestdio.h#includestdlib.h#includestring.h#includemath.h#definetrue1#definefalse0#defineOPSETSIZE8typedefintStatus;unsignedcharPrior[8][8]={//运算符优先级表//'+''-''*''/''('')''#''^'/*'+'*/'','','','','','','','',/*'-'*/'','','','','','','','',/*'*'*/'','','','','','','','',/*'/'*/'','','','','','','','',/*'('*/'','','','','','=','','',/*')'*/'','','','','','','','',/*'#'*/'','','','','','','=','',/*'^'*/'','','','','','','',''};typedefstructStackChar{charc;structStackChar*next;}SC;//StackChar类型的结点SCtypedefstructStackFloat{floatf;structStackFloat*next;}SF;//StackFloat类型的结点SFSC*Push(SC*s,charc){//SC类型的指针Push，返回pSC*p=(SC*)malloc(sizeof(SC));p-c=c;p-next=s;returnp;}SF*Push(SF*s,floatf){//SF类型的指针Push，返回pSF*p=(SF*)malloc(sizeof(SF));p-f=f;p-next=s;returnp;}SC*Pop(SC*s){//SC类型的指针PopSC*q=s;s=s-next;free(q);returns;}SF*Pop(SF*s){//SF类型的指针PopSF*q=s;s=s-next;free(q);returns;}floatOperate(floata,unsignedchartheta,floatb){//计算函数Operateswitch(theta){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':returna/b;case'^':returnpow(a,b);default:return0;}}charOPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'};StatusIn(charTest,char*TestOp){intFind=false;for(inti=0;iOPSETSIZE;i++){if(Test==TestOp[i])Find=true;}returnFind;}ReturnOpOrd(charop,char*TestOp){for(inti=0;iOPSETSIZE;i++)if(op==TestOp[i])returni;}charprecede(charAop,charBop){returnPrior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];}floatEvaluateExpression(char*MyExpression){//算术表达式求值的算符优先算法//设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合SC*OPTR=NULL;//运算符栈，字符元素SF*OPND=NULL;//运算数栈，实数元素charTempData[20];floatData,a,b;chartheta,*c,x,Dr[]={'#','\0'};OPTR=Push(OPTR,'#');c=strcat(MyExpression,Dr);strcpy(TempData,\0);//字符串拷贝函数while(*c!='#'||OPTR-c!='#'){if(!In(*c,OPSET)){Dr[0]=*c;strcat(TempData,Dr);//字符串连接函数c++;if(In(*c,OPSET)){Data=atof(TempData);//字符串转换函数(double)OPND=Push(OPND,Data);strcpy(TempData,\0);}}else{//不是运算符则进栈switch(precede(OPTR-c,*c)){case''://栈顶元素优先级低OPTR=Push(OPTR,*c);c++;break;case'='://脱括号并接收下一字符OPTR=Pop(OPTR);c++;break;case''://退栈并将运算结果入栈theta=OPTR-c;OPTR=Pop(OPTR);b=OPND-f;OPND=Pop(OPND);a=OPND-f;OPND=Pop(OPND);OPND=Push(OPND,Operate(a,theta,b));break;}//switch}}//whilereturnOPND-f;}//EvaluateExpressionvoidmain(){charstr1[128],s[128];floatss;puts(请输入表达式:);gets(s);printf(%s\b=%g\n,s,EvaluateExpression(s));}