表达式求值
时间限制：
3000ms | 内存限制：
65535KB
难度：
4
- 描述
-
ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。
比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）- 输入
-
第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0 - 输出
- 每组都输出该组运算式的运算结果，输出结果保留两位小数。
- 样例输入
-
2 1.000+2/4= ((1+2)*5+1)/4=
- 样例输出
-
1.50 4.00
-
#include<stdio.h> #include<string.h> #include<stdlib.h> /* 利用栈和队列操作，栈储存运算符，队列可以得到最后的后缀表达式，转换后再次用栈进行计算，最后求得结果 */ int compare( char ch ){ if( ch == '(' ) return 0; if( ch == '+' ) return 1; if( ch == '-' ) return 1; if( ch == '*' ) return 2; if( ch == '/' ) return 2; } int searchD( char sh[] ){ int l = strlen(sh); int i; for( i = 0 ; i < l ; ++i ) if( sh[i] == '.') return i; return l; } int main(){ int n,i,j,l,opr_i,opr_j,isnum,exp_i,res_i; char s[1010]; char opr[1010][10]; char exp[1010][2]; char temp[10]; double res[1010],dd; scanf("%d",&n); while(n--){ scanf("%s",s); memset(opr,'\0',sizeof(opr)); memset(exp,sizeof(exp)); memset(res,sizeof(res)); i = opr_i = opr_j = exp_i = res_i = 0; while( s[i] != '=' ){ j = isnum = 0; while( (s[i]>='0' && s[i]<='9') || s[i]=='.' ){ isnum = 1; temp[j++] = s[i++]; } if( isnum ){ temp[j] = '\0'; strcpy( opr[opr_i++],temp ); } else{ temp[0] = s[i++]; temp[1] = '\0'; switch( temp[0] ){ case '(':strcpy( exp[exp_i++],temp );break; case '+': case '-': case '*': case '/':if( exp_i != 0 ) while( compare(temp[0]) <= compare(exp[exp_i-1][0]) ){ strcpy( opr[opr_i++],exp[--exp_i] ); if( exp_i == 0 ) break; } strcpy( exp[exp_i++],temp );break; case ')':while( exp[exp_i-1][0] != '(' ){ strcpy( opr[opr_i++],exp[--exp_i] ); } --exp_i;break; } } } while( exp_i >= 0 ) strcpy( opr[opr_i++],exp[--exp_i] ); for( ; opr_j <= opr_i ; ++opr_j ){ if( opr[opr_j][0] >= '0' && opr[opr_j][0] <= '9' ){ dd = 0; int x = 1,z,d ; double y = 0.1; d = z = searchD( opr[opr_j] ); --d;++z; while( d >= 0 ){ dd += ( ( opr[opr_j][d] - '0' ) * x ); x*=10; --d; } while( opr[opr_j][z] != '\0' ){ dd += ( ( opr[opr_j][z] - '0' ) * y ); y*=0.1; ++z; } res[res_i++] = dd; } else{ switch( opr[opr_j][0] ){ case '+':res[res_i-2] += res[res_i-1];break; case '-':res[res_i-2] -= res[res_i-1];break; case '*':res[res_i-2] *= res[res_i-1];break; case '/':res[res_i-2] /= res[res_i-1];break; } res_i--; } } printf("%.2lf\n",res[0]); } return 0; }
