栈的应用：表达式求值1

《数据结构课程设计实验一：表达式求值》实验报告一、简介要求设计一个表达式求值的程序。该程序必须可以接受包含〔，〕，+，-，*，/，%，和^〔求幂运算符，a^b=ab〕的中缀表达式，并求出结果。如果表达式正确，那么输出表达式的结果；如果表达式非法，那么输出错误信息。输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，那么每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值〔精确到小数点后两位〕，也可能是错误信息“ERRORININFIXNOTATION”。输入例子：1+2+3-44.99+5.99+6.99*1.062^2.5^3(5.6-2)%35%(3.2-2.1)+1输出例子：2.0018.3950535.16Errorininfixnotation.Errorininfixnotation.Errorininfixnotation.输入的表达式是由操作数和运算符以及改变运算顺序的圆括号连接而成的式子。由于不同的运算符间存在优先级，同一优先级的运算间又存在着运算结合顺序的问题〔即左结合，还是右结合〕，所以简单的从左到右计算是不充分的。而后缀表达式〔后缀表达式是由一系列的运算符、操作数组成，其中运算符位于两个操作数之后，如123*+〕那么很容易通过应用栈实现表达式的计算，所以，我们要先把中缀表达式转换成后缀表达式，再进行计算。二、算法说明a、定义一个栈存放运算符，将中缀表达式转化为后缀表达式。根本过程如下：如果遇到空格，那么认为是分隔符，不需处理。如遇到操作数，那么直接输出。假设遇到左括号，那么将其压入栈中。假设是遇到右括号，说明括号的中缀表达式已经扫描完毕，把括号中的运算符退栈，并输出。假设遇到是运算符，当该运算符的优先级别大于栈顶运算符的优先级别时，那么将它压栈；当该运算符的优先级别小于栈顶运算符的优先级别时，那么将栈顶运算符退栈并输出，再次比拟新的栈顶运算符，按同样方法处理，直到该运算符大于栈顶运算符的优先级为止，然后将该运算符压栈。假设中缀表达式处理完毕，那么要把栈中存留的运算符一并输出。其中，不同运算符优先级的设置可以用一个数来代表其优先级，优先级越高，数值就越大。程序中，加减运算符的优先级是1，乘除法和取模运算符的优先级是2，求幂运算符的优先级是3，右括号是5，左括号是6，其他为0。运算符优先级关系如表1-1。.b、转化后，用栈实现后缀表达式的计算。其根本过程是：当输入一个操作数时，它被压入栈中，当一个运算符出现时，就从栈中弹出适当数量的操作数，对该运算进行计算，计算结果再压入栈中。对于常见的二元运算符来说，弹出的操作数只有两个。处理完整个后缀表达式之后，栈顶上的元素就是表达式的结果值。整个计算过程不需要理解运算的优先级规那么。表1-1运算符优先级关系表+-*/()^+==<<<<<-==<<<<<*>>==<<</>>==<<<(>>>>=>>)>>>><=>^>>>><<=程序的整体算法过程分两步：第一步，从“input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换为后缀表达式，将输出结果〔转换后得到的后缀表达式〕存放在一个temp文件中。第二步，从temp文件中读取后缀表达式，并应用操作数栈Operands计算后缀表达式结果，将结果输出到“output.txt”文件中。对于求幂运算要特别注意，例如2^3^3要变成223^，因为求幂运算符是从右到左结合的。本程序中的栈采用前面所述的带头结点的链式存储结构，涉及两种类型：用于存储运算符号的char类型的链栈以及用于存储操作数的float类型的链栈。Char类型的栈“Whereat”用来记录后缀表达式中操作数和运算符号的顺序，以及决定需要多少次运算。其中以A=Operand,B=Operator区分〔例如1+2转换成12+，再Whereat中的形式应该是AAB〕。三、测试结果四、结果分析与总结该程序包括了许多可能出现的情况。测试包括正确的表达式，错误的表达式。因本程序曾加了输出分类局部，所以输出的结果包括了运算符错误，操作数错误，其他错误。附录：源代码/*将中缀表带式转换为后缀表达式*/voidConvertToPost(FILE*In,StackWhereat,FILE*Temp){ StackOpHolder; charholder; charlastseen; intdigitcounter=0;//操作数的计数器 OpHolder=(PtrToNode)malloc(sizeof(structNode));//初始化 OpHolder->Next=NULL; holder=getc(In);//读入 lastseen='@';//用来防止输入格式错误，例如两个小数点 putc('',Temp); while((holder!='\n')&&(holder!=EOF)){ if(holder=='')//空字符，跳过{ digitcounter=0;//操作数计数器记0 } elseif(IsOperator(holder)==-1)//如果holder不是操作数或运算符号{ PrintError=3; //其他错误 } elseif(IsOperator(holder)==0)//如果holder是操作数{ if((lastseen==holder)&&(lastseen=='.'))//错误处理{ PrintError=2; //操作数出错 } else lastseen=holder; if(digitcounter==0){ Push('A',Whereat);//进栈 digitcounter++; //计数器加一 putc('',Temp); } putc(holder,Temp);//将holder放入Temp文件 } else{ digitcounter=0; if((lastseen==holder)&&(lastseen!='(')&&(lastseen!=')')){//"("情况特殊对待PrintError=1;//运算符出错} else lastseen=holder; if(IsEmpty(OpHolder)==1)//当OpHolder为空{ Push(holder,OpHolder);//将holder进到栈OpHolder } elseif(OperatorValue(Top(OpHolder))==6)//OpHolder是"("的情况{ if(OperatorValue(holder)==5)//holder是")"的情况 Pop(OpHolder);//弹栈 else Push(holder,OpHolder); } elseif(OperatorValue(holder)==6)//holder是"〔"的情况{ Push(holder,OpHolder); } elseif(OperatorValue(holder)==5){//OpHolder是")"的情况 while((IsEmpty(OpHolder)!=1)&&(OperatorValue(Top(OpHolder))!=6)) { putc('',Temp); Push('B',Whereat);//B进栈 putc(Top(OpHolder),Temp); Pop(OpHolder); } if(IsEmpty(OpHolder)==1)//错误处理,括号不匹配{ PrintError=1; } else Pop(OpHolder); } elseif((OperatorValue(holder)==OperatorValue(Top(OpHolder))) &&(OperatorValue(holder)==3))//幂运算情况{ Push(holder,OpHolder); } elseif((OperatorValue(holder)<OperatorValue(Top(OpHolder))) &&OperatorValue(Top(OpHolder))==3)//幂运算情况{ putc('',Temp); Push('B',Whereat); putc(Top(OpHolder),Temp); Pop(OpHolder); while((IsEmpty(OpHolder)!=1)&&(OperatorValue(Top(OpHolder))==3)) { Push('B',Whereat); putc('',Temp); putc(Top(OpHolder),Temp); Pop(OpHolder); } Push(holder,OpHolder); }//如果当前运算符号的优先级小于或者等于堆栈中的运算符号的优先级,那么将其放入temp中，并且将堆栈中的运算符号出栈，放入temp中，直到堆栈为空或者优先级小于堆栈顶元素的优先级 elseif(OperatorValue(Top(OpHolder))>=OperatorValue(holder)){//栈不空且左括号外的栈顶优先级大于holder优先级while((IsEmpty(OpHolder)!=1)&&(OperatorValue(Top(OpHolder))>=OperatorValue(holder)) &&(OperatorValue(Top(OpHolder))!=6)) { putc('',Temp); putc(Top(OpHolder),Temp); Push('B',Whereat); Pop(OpHolder); } Push(holder,OpHolder); } elseif(OperatorValue(Top(OpHolder))<OperatorValue(holder)){//如果当前运算符号的优先级大于堆栈中的运算符号的优先级,那么将其压入堆栈中Push(holder,OpHolder); } } holder=getc(In); //继续读入 } //While循环结束 while(IsEmpty(OpHolder)!=1){//最后如果堆栈中还有运算符号，那么一并放到temp中 Push('B',Whereat); putc('',Temp); putc(Top(OpHolder),Temp); Pop(OpHolder); } MakeEmpty(OpHolder);//使栈空 free(OpHolder);//释放栈}/*计算后缀表达式*/voidCalculate(FILE*Change,StackWhereat,FILE*Temp){ FStackOperands; floatlooker; charOp; charspacefinder; floatanswer=0; floatNumA; floatNumB; Operands=(Ptr_Fn)malloc(sizeof(structFNode)); Operands->Next=NULL; while((IsEmpty(Whereat)!=1)&&PrintError==0){//循环直到Whereat空，或者遇到错误 if(Top(Whereat)=='A'){ fscanf(Temp,"",&spacefinder); fscanf(Temp,"%f",&looker); //如果是A,那么是操作数 FPush(looker,Operands); //将浮点数放入Operands Pop(Whereat); } elseif(Top(Whereat)=='B')//如果是B,那么是运算符{ fscanf(Temp,"",&spacefinder); Op=getc(Temp); switch(Op) { //判断是什么运算符 case('^')://幂运算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands))//错误处理{ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); if((NumA==0&&NumB<0)||((NumA<0)&&(NumB-(int)NumB!=0))) {//其他字符 PrintError=2;//操作数错误 } else{ answer=pow(NumA,NumB); FPush(answer,Operands); } } break; case'%'://取模运算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands))//错误处理{ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); if((NumA-(int)NumA!=0)||(NumB-(int)NumB!=0) ||(NumB==0))//是整数或0 { PrintError=2; } else{ answer=(int)NumA%(int)NumB; //xmodb FPush(answer,Operands); } } break; case'*'://乘法运算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands)){ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); answer=NumA*NumB; //x*y FPush(answer,Operands); } break; case'/'://除法运算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands)){ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); if(NumB==0){ PrintError=2; //分母不为0 } else{ answer=(float)(NumA/NumB); //x/y FPush(answer,Operands); } } break; case'+'://加法运算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands)){ PrintError=3; } else{ NumA=FTop(Operands); FPop(Operands); answer=NumA+NumB; //x+y FPush(answer,Operands); } break; case'-'://减法运算 NumB=FTop(Operands); FPop(Operands); if(FIsEmpty(Operands)){ PrintError=3; } else{ NumA=FTop(Operands); FPo