九、表达式求值（1）

文章目录

九、表达式求值（1）题目描述解题思路上机代码

题目描述

背景：

我们的教材中已经介绍了表达式求值的算法，现在我们将该算法的功能进行扩展，要求可以处理的运算符包括：+、-、*、/、%（整数取余）、^（乘方）、（、）。

要求：

采用算符优先算法，计算的中间结果只保留整数。

输入：

第一行为整数N。表示下面有N个表达式

从第二行起的后面N行为N个由整数构成的表达式

输出：

共N行，每行为相应表达式的计算结果。

如果判断出表达式有错误，则输出：error.

如果在计算过程中出现除数为0的情况，则输出：Divide 0.

特殊情况说明：

在表达式中，如果操作数出现负数（例如-8），则要特别注意。例如： 10加-8表示为：10±8。 10减-8表示为：10–8。

测试输入期待的输出时间限制内存限制额外进程测试用例 142^32^02^3^22^(3-1)^(10-8)81512161秒64M0测试用例 211(2+82+8)8/08/(8+5-13)2^(2-5)10-(80-30(/3*3+410-80-30)/3*3+4(2+8)(3+2)(2)3(8)30(/3+3)+410(20-8)+2error.error.Divide 0.Divide 0.error.error.error.error.error.error.error.1秒64M0测试用例 3210(10)14*10-(10)2error.error.1秒64M0测试用例 41418-3218/418%310+20*410-20/4(18-3)*310*(10)(10+2)/(8-10)(2*3)/(5*2)10-(80-30)/3*3+4(((2+8)*2-(2+4)/2)*2-8)*2(((8+2)*(4/2)))10/0(10-80*2-144090545100-60-345220Divide 0.error.1秒64M0

解题思路

算符优先算法的思路不管是在PPT还是教材中已经给出了详细说明，我们再回顾一下

从左向右扫描表达式：

遇操作数，保存；遇运算符号 ${\theta }_j$，与刚处理过的运算符 ${\theta }_i$ 比较： 若 ${\theta }_i<{\theta }_j$ 则保存 ${\theta }_j$（已存入栈中的运算符的优先关系为 ${\theta }_1<{\theta }_2<{\theta }_3$···）若 ${\theta }_i>{\theta }_j$ 则说明 ${\theta }_i$ 是已扫描过的运算符中优先级最高的，可进行运算若 ${\theta }_i={\theta }_j$ 则说明括号内算式已算完，需消去括号

算符优先算法用两个工作栈：OPTR栈保存运算符；一个是OPND栈保存操作数或运算结果。

基本思想

1.将操作数栈置空，表达式起始符“#”入栈（运算符栈的栈底元素）。

2.依次读入表达式中的每一项(有完整意义)，若是操作数，则进OPND栈；若是运算符，则与OPTR栈的栈顶运算符比较优先级后作相应操作， 直至表达式求值完毕（即OPTR栈顶元素和当前读入字符均为“#”）

Tips：

老师上课时认真讲了这个算法，并预留了这个算法关于 C 语言实现的代码，相信细心的同学已经注意到了。但是这段代码是不能直接通过这个题的，有一些小的 bug 需要我们进行处理。因此我们可以选择理解代码的逻辑，针对具体 bug 进行订正即可。

上机代码

#include<stdlib.h> #include<stdio.h> #include<string.h> #include<math.h> #define Nul 0x00 char chinput[200], *p; /* 运算式存储字符串,运算式当前读取位置 */ int operationgFlag=0; /* operationgFlag=1时意味着出现除数为0的情况 */ struct t /* 符号栈 */ { char dat[200]; int top; }prt; struct d /* 数字栈 */ { long int dat[200]; int top; }prd; char PRI[9][9]= /* 优先级表 */ { {'>','>','<','<','<','<','<','>','>'}, {'>','>','<','<','<','<','<','>','>'}, {'>','>','>','>','<','<','<','>','>'}, {'>','>','>','>','<','<','<','>','>'}, {'>','>','>','>','>','<','<','>','>'}, {'>','>','>','>','>','<','<','>','>'}, {'<','<','<','<','<','<','<','=',Nul}, {'>','>','>','>','>','>',Nul,'>','>'}, {'<','<','<','<','<','<','<',Nul,'='} }; void pushd( long int a ) /* 数字入栈 */ { prd.dat[ prd.top++ ]=a; } void pusht( char a ) /* 符号入栈 */ { prt.dat[ prt.top++ ]=a; } long int popd( ) /* 数字出栈 */ { return prd.dat[ --prd.top ]; } char popt( ) /* 符号出栈 */ { return prt.dat[ --prt.top ]; } long int numble() /* 数字整理 */ { long int b=0; do { b = b*10 + *p -'0'; // 组成整数 p++; } while ( *p>='0' && *p<='9' ) ; return b; } long operation( long int x, long int y, char a ) { switch( a ) { case '+': return x+y; case '-': return x-y; case '*': return x*y; case '/': if ( y ) return x/y; else { printf("Divide 0.\n"); operationgFlag=1; return 0;} case '%': return ((long int) fmod(x,y)); case '^': if (y>=0 ) return pow(x,y); else { printf("error.\n"); operationgFlag=1; return 0;} } } int signswitch( char a ) /* 符号转换 */ { switch( a ) { case '+': return 0; case '-': return 1; case '*': return 2; case '/': return 3; case '%': return 4; case '^': return 5; case '(': return 6; case ')': return 7; case '#': return 8; } } char refusal( char a,char b ) /* 判定优先级 */ { return PRI[signswitch(a)][signswitch(b)]; } int main() { int i,j,n,k,l, flag=0; /* flag=0前一个符号不是) */ scanf("%d",&n); while(n--) { //初始化 operationgFlag = 0; flag = 0; char b; prt.dat[0] = '#'; prt.top = 1; prd.top = 0; scanf("%s", chinput); /* 接收运算式 */ strcat ( chinput, "#"); /* 在运算式结尾加#号 */ p = chinput; while ( *p!='#' || prt.dat[prt.top-1]!='#' ) //表达式中还有值或者栈中还有值 { if ( *p>='0' && *p<='9') { j = numble(); /* 如果是数字进行整理并入栈 */ pushd( j ); } else /* 如果是符号与栈顶的符号比较并运算 */ { if ( flag==1 && *p=='(' ) { printf("error.\n"); goto h; } else if ( *p==')') flag = 1; else flag = 0; switch ( refusal(prt.dat[prt.top-1], *p ) ) { case '<': pusht ( *p++ ); break; /* 高则入栈 */ case '=': popt( ); /* 脱括号 */ p++; break; case '>': b = popt(); /* 低则进行栈顶计算 */ k = popd(); /* 第二操作数出栈 */ l = popd(); /* 第一操作数出栈 */ k = operation(l,k,b); /* 计算 */ if(operationgFlag==1) goto h; else{ pushd(k); break; /* 计算结果入栈 */ } case Nul: printf("error.\n"); goto h; } } } if(prd.top-1 == 0) //数字栈中只有一个数，那就是最终结果 printf("%d\n",prd.dat[prd.top-1]); /* 输出 */ else printf("error.\n"); h:; /* 继续下一个 */ /*有三处需要直接进入下一次循环，goto不失是个好方法*/ } return 0; }