《栈的应用：表达式求值1》由会员分享，可在线阅读，更多相关《栈的应用：表达式求值1（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计实验一：表达式求值实验报告一、简介要求设计一个表达式求值的程序。该程序必须可以接受包含（，），+，-，*, /, %，和人（求幂运算符，aAb=ab）的中缀表达式，并求出结果。如果表 达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。输入要求：程序从“ input.txt ”文件中读取信息，在这个文件中如果有多个中缀表 达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将其结果放在“o utput.txt ”文件的每一行中。这些 结果可能是值（精确到小数点后两位），也可能是错误信息“ERROR IN INFIX NOTATIO
2、N”。输入例子：1+2+3-44.99+5.99+6.99*1.062A2.5A3（5.6-2）%35%（3.2-2.1）3.0.2+1输出例子：2.0018.3950535.16Error in infix notation.Error in infix notation.Error in infix notation.输入的表达式是由操作数和运算符以及改变运算顺序的圆括号连接而 成的式子。由于不同的运算符间存在优先级，同一优先级的运算间又存在着 运算结合顺序的问题（即左结合，还是右结合），所以简单的从左到右计算 是不充分的。而后缀表达式（后缀表达式是由一系列的运算符、操作数组成， 其中运算
3、符位于两个操作数之后，如123*+）则很容易通过应用栈实现表达 式的计算，所以，我们要先把中缀表达式转换成后缀表达式，再进行计算。二、算法说明a、 定义一个栈存放运算符，将中缀表达式转化为后缀表达式。基本过程如下： 如果遇到空格，则认为是分隔符，不需处理。如遇到操作数，则直接输出。若遇到左括号，则将其压入栈中。 若是遇到右括号，表明括号的中缀表达式已经扫描完毕，把括号中的运算符 退栈，并输出。 若遇到是运算符，当该运算符的优先级别大于栈顶运算符的优先级别时，则 将它压栈；当该运算符的优先级别小于栈顶运算符的优先级别时，则将栈顶 运算符退栈并输出，再次比较新的栈顶运算符，按同样方法处理，直到该运
4、 算符大于栈顶运算符的优先级为止，然后将该运算符压栈。 若中缀表达式处理完毕，则要把栈中存留的运算符一并输出。 其中，不同运算符优先级的设置可以用一个数来代表其优先级，优先级越高，数 值就越大。程序中，加减运算符的优先级是 1，乘除法和取模运算符的优先级是 2，求幂运算符的优先级是 3，右括号是 5，左括号是 6，其他为 0。运算符优先 级关系如表 1-1。 .b、转化后，用栈实现后缀表达式的计算。其基本过程是：当输入一个操作数时，它被压入栈中，当一个运算符出现时， 就从栈中弹出适当数量的操作数，对该运算进行计算，计算结果再压入栈中。对 于常见的二元运算符来说，弹出的操作数只有两个。处理完整个
5、后缀表达式之后， 栈顶上的元素就是表达式的结果值。整个计算过程不需要理解运算的优先级规 则。表 1-1 运算符优先级关系表+-*/()A+=-=)ANext = NULL;holder=getc(In); /读入lastseen = ; /用来防止输入格式错误，例如两个小数点 putc( ,Temp);while (holder !=n) & (holder != EOF)if (holder = ) /空字符，跳过digitcounter = 0; /操作数计数器记0else f (IsOperator(holder) =-1)/如果 holder 不是操作数或运算符号PrintError
6、= 3;/其他错误else f (IsOperator(holder)=0)/如果 holder 是操作数if (lastseen = holder) & PrintError = 2;elselastseen = holder;if (digitcounter = 0) Push(A,Whereat);digitcounter+;(lastseen = .) /错误处理/操作数出错/进栈/计数器加一putc( ,Temp);putc(holder,Temp);elsedigitcounter = 0;if (lastseen = holder) & /(情况特殊对待 PrintError =
7、 1;else lastseen = holder;if(IsEmpty(OpHolder)=1)Push(holder,OpHolder);/将holder放入Temp文件(lastseen != () & (lastseen != )/运算符出错/当 OpHolder 为空/将 holder 进到栈 OpHolder/OpHolde r是（的情况/ holder是）的情况/弹栈/ holder是（的情况else if(OperatorValue(Top(OpHolder) = 6) if(OperatorValue(holder)=5) Pop(OpHolder);else Push(ho
8、lder,OpHolder);else if(OperatorValue(holder) = 6)Push(holder,OpHolder);else if(OperatorValue(holder) = 5) /OpHolde r 是)的情况while(IsEmpty(OpHolder)!=1)&(OperatorValue(Top(OpHolder)!=6)putc( ,Temp);Push(B,Wherea t);/B 进栈putc(Top(OpHolder),Temp);Pop(OpHolder);if (IsEmpty(OpHolder) = 1) /错误处理,括号不匹配 Print
9、Error = 1;elsePop(OpHolder);else if(OperatorValue(holder) = OperatorValue(Top(OpHolder)& (OperatorValue(holder) = 3) /幂运算情况Push(holder,OpHolder);else if(OperatorValue(holder) = OperatorValue(holder)/栈不空且左括号外的栈顶优先级大于holder优先级whil e(IsEmpty(OpHo l der)!= 1)&(OperatorValue(Top(OpHo l der) = OperatorVal
10、ue(holder) & (OperatorValue(Top(OpHolder)!=6) putc( ,Temp);putc(Top(OpHolder),Temp);Push(B,Whereat); Pop(OpHolder);Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) OperatorValue(holder)/如果当前运算符号的优先级大于堆栈中的运算符号的优先级,则将其压入堆栈中 Push(holder,OpHolder);/继续读入holder=getc(In);/While循环结束while(IsEmpty(OpHolder)!=1)/最后如果堆栈中还有运算符号，贝9一并放到temp中 Push(B,Whereat);putc( ,Temp); putc(Top(OpHolder),Temp);Pop(OpHolder);MakeEmpty(OpHolder);/使栈空free(OpHolder);/释放栈
