表达式求值

题目代码

题目

背景：

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

要求：

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

输入：

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

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

输出：

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

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

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

特殊情况说明：

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

 测试输入期待的输出时间限制内存限制额外进程测试用例 1以文本方式显示 4↵2^3↵2^0↵2^3^2↵2^(3-1)^(10-8)↵ 以文本方式显示 8↵1↵512↵16↵ 1秒64M0测试用例 2以文本方式显示 11↵(2+8↵2+8)↵8/0↵8/(8+5-13)↵2^(2-5)↵10-(80-30(/3*3+4↵10-80-30)/3*3+4↵(2+8)(3+2)↵(2)3(8)↵30(/3+3)+4↵10(20-8)+2↵ 以文本方式显示 error.↵error.↵Divide 0.↵Divide 0.↵error.↵error.↵error.↵error.↵error.↵error.↵error.↵ 1秒64M0测试用例 3以文本方式显示 2↵10(10)↵14*10-(10)2↵ 以文本方式显示 error.↵error.↵ 1秒64M0测试用例 5以文本方式显示 14↵18-32↵18/4↵18%3↵10+20*4↵10-20/4↵(18-3)*3↵10*(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↵ 以文本方式显示 -14↵4↵0↵90↵5↵45↵100↵-6↵0↵-34↵52↵20↵Divide 0.↵error.↵ 1秒64M0

代码

#include <stdio.h> #include <stdlib.h> #include<string.h> #include<math.h> char pro[9][9]={ {'>','>','<','<','<','>','>','<','<'}, //运算符优先顺序表。 {'>','>','<','<','<','>','>','<','<'}, //应当注意！！！ {'>','>','>','>','<','>','>','<','>'}, //相同两个运算符若处在前后两不同位置 {'>','>','>','>','<','>','>','<','>'}, //其优先性也随之变化!! {'<','<','<','<','<','=',' ','<','<'}, {'>','>','>','>',' ','>','>','>','>'}, {'<','<','<','<','<',' ','=','<','<'}, {'>','>','>','>','<','>','>','<','>'}, //该优先性顺序, {'>','>','>','>','<','>','>','<','>'} //对应下面的Opt数组顺序 }; int op(int a, int b, char opt) { if(opt=='+') { return a+b; } else if(opt=='-') { return a-b; } else if(opt=='*') { return a*b; } else if(opt=='/') { if(b==0) { printf("Divide 0.\n"); return 0x3f3f3f3f; } else { return a/b; } } else if(opt=='%') { return a%b; } else if(opt=='^') { if(b>=0) { return pow(a,b); } else { printf("error.\n"); return 0x3f3f3f3f; } } else { printf("error.\n"); return 0x3f3f3f3f; } } int shu[100010]; char opt[100010]; char ex[100010]; int main() { int N; int i,j,k,m,n,a,b; int flag=0; int flag1=0; int flag2=0; int flag3=0; int flag4=0; int flag5=0; char Opt[9]={'+','-','*','/','(',')','#','^','%'}; memset(ex,'\0',sizeof(ex)); int exp=0,shup=-1,optp=-1; scanf("%d",&N); while(N--) { char c; flag=2; flag1=0; flag2=0; flag3=0; flag4=0; flag5=0; k=0; int fuckyou=0; scanf("%s",ex); strcat(ex,"#"); //结束判断 opt[++optp]='#'; //同理 for(a=0;a<=strlen(ex)-3;a++) { flag5=0; int fuck=a; if(ex[fuck]=='+'||ex[fuck]=='-'||ex[fuck]=='*'||ex[fuck]=='/'||ex[fuck]=='%'||ex[fuck]=='^') { flag5++; fuck++; } if(ex[fuck]=='+'||ex[fuck]=='-'||ex[fuck]=='*'||ex[fuck]=='/'||ex[fuck]=='%'||ex[fuck]=='^') { flag5++; fuck++; } if(ex[fuck]=='+'||ex[fuck]=='-'||ex[fuck]=='*'||ex[fuck]=='/'||ex[fuck]=='%'||ex[fuck]=='^') { flag5++; fuck++; } if(flag5>=3) { printf("error.\n"); memset(ex,'\0',sizeof(ex)); memset(shu,0,sizeof(shu)); memset(opt,'\0',sizeof(opt)); shup=-1; flag1++; exp=0; flag5=0; optp=-1; fuckyou++; break; } } while(ex[exp]!='#'||opt[optp]!='#') { if(fuckyou!=0) { break; } if(ex[exp]>='0'&&ex[exp]<='9') { if(flag==0) { int aaa=0; aaa=shu[shup--]*10+(ex[exp++]-'0'); shu[++shup]=aaa; flag=0; } else { shu[++shup]=ex[exp++]-'0'; flag=0; } } else { if(flag4==1) { shu[0]*=-1; flag4=0; } if(flag==1) { if(ex[exp]=='+'||ex[exp]=='-'||ex[exp]=='*'||ex[exp]=='/'||ex[exp]=='^'||ex[exp]=='%') { printf("error.\n"); flag1++; memset(ex,'\0',sizeof(ex)); memset(shu,0,sizeof(shu)); memset(opt,'\0',sizeof(opt)); shup=-1; optp=-1; exp=0; break; } } if(ex[exp]=='(') { flag=1; int s=exp+1; int d=s+1; if(ex[s]=='-'&&ex[d]>='0'&&ex[d]<='9') { flag=2; flag4=1; exp=s+1; opt[++optp]='('; continue; //gshfgdfhj } } else { flag=2; } if(optp==-1) { printf("error.\n"); memset(ex,'\0',sizeof(ex)); memset(shu,0,sizeof(shu)); memset(opt,'\0',sizeof(opt)); flag1++; shup=-1; optp=-1; exp=0; break; } else { char com=opt[optp--]; char Ex; for(i=0;i<9;i++) { if(Opt[i]==com) { m=i; } if(Opt[i]==ex[exp]) { n=i; } } Ex=pro[m][n]; if(Ex=='<') { if(exp==0&&ex[exp]=='-') { flag4=1; exp++; optp++; continue; } opt[++optp]=com; opt[++optp]=ex[exp++]; continue; } else if(Ex=='=') { exp++; continue; } else if(Ex==' ') { printf("error.\n"); memset(ex,'\0',sizeof(ex)); memset(shu,0,sizeof(shu)); memset(opt,'\0',sizeof(opt)); shup=-1; flag1++; exp=0; optp=-1; break; } else { int q=exp-1; if(ex[exp]=='-') { if(ex[q]=='('||ex[q]=='*'||ex[q]=='/'||ex[q]=='%'||ex[q]=='+'||ex[q]=='-') { opt[++optp]=com; exp++; flag2=1; continue; } } if(flag2==1) { shu[shup]*=-1; flag2=0; } if(flag3==1) { shu[--shup]*=-1; shup++; flag3=0; } b=shu[shup--]; a=shu[shup--]; k=op(a,b,com); if(k==0x3f3f3f3f) { memset(ex,'\0',sizeof(ex)); shup=-1; optp=-1; exp=0; memset(shu,0,sizeof(shu)); memset(opt,'\0',sizeof(opt)); break; } else { shu[++shup]=k; } continue; } exp++; } } } if(shup==0&&optp==0) { if(flag4==1) { printf("%d\n",-shu[shup]); flag4=0; } else { printf("%d\n",shu[shup]); } } else { if(k!=0x3f3f3f3f&&flag1==0) { printf("error.\n"); } } memset(ex,'\0',sizeof(ex)); memset(shu,0,sizeof(shu)); memset(opt,'\0',sizeof(opt)); exp=0; fuckyou=0; shup=-1; flag1=0; optp=-1; } return 0; } //出现负数之后立即记录。