表达式求值

时间限制：3000 ms | 内存限制：65535 KB

难度：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

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<stack>
  4 #include<cstring>
  5 #include<stdlib.h>
  6 #define OPSETSIZE 7
  7 using namespace std;
  8 
  9 char OPSET[OPSETSIZE]={'+','-','*','/','(',')','='};
 10 unsigned char Prior[7][7] = {     //  算符间的优先关系
 11      '>','>','<','<','<','>','>',
 12    '>','>','<','<','<','>','>',
 13    '>','>','>','>','<','>','>',
 14    '>','>','>','>','<','>','>', 
 15    '<','<','<','<','<','=',' ',
 16    '>','>','>','>',' ','>','>',
 17    '<','<','<','<','<',' ','='
 18 };  
 19 char s[1002];
 20 int lg;
 21 
 22 bool In(char Test,char* TestOp) {
 23    bool Find=false;
 24    for (int i=0; i< OPSETSIZE; i++) {
 25       if (Test == TestOp[i]) Find= true;
 26    }
 27    return Find;
 28 }//判断是否为运算符
 29 
 30 float Operate(float a,unsigned char theta, float b) {
 31    switch(theta) {
 32       case '+': return a+b; 
 33       case '-': return a-b;
 34       case '*': return a*b;
 35       case '/': return a/b;
 36       default : return 0;
 37    } 
 38 }//运算 
 39 
 40 
 41 int ReturnOpOrd(char op,char* TestOp) {
 42    int i;
 43    for(i=0; i< OPSETSIZE; i++) {
 44       if (op == TestOp[i]) return i;
 45    }
 46    return 0;
 47 }//获得运算符序号
 48 
 49 char precede(char Aop, char Bop) {
 50    return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
 51 }//ReturnOpOrd和precede组合，判断运算符优先级
 52 
 53 
 54 float EvaluateExpression() {  
 55    // 算术表达式求值的算符优先算法。
 56    // 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。
 57    stack<char>  OPTR;    // 运算符栈，字符元素
 58    stack<float> OPND;    // 运算数栈，实数元素
 59    float a,b,data;
 60    char theta,c,num[20],Dr[2];
 61    
 62    strcpy(num,"\0");
 63    OPTR.push('='); 
 64    c=getchar();
 65    while(c!='='|| OPTR.top()!='=')
 66    {
 67             if(!In(c,OPSET)) 
 68       {
 69         Dr[0]=c;
 70       Dr[1]='\0';//存放单个数
 71         strcat(num,Dr);//将单个数连到TempData中，形成字符串
 72         c=getchar();
 73         if(In(c,OPSET))//如果遇到运算符，则将字符串TempData转换成实数，入栈，
 74                         并重新置空
 75    {
 76             data=(float)atof(num);
 77             OPND.push(data);
 78             strcpy(num,"\0");
 79          }                 
 80       } 
 81       else 
 82       {
 83           // 不是运算符则进栈
 84          switch (precede(OPTR.top(), c)) 
 85          { 
 86             case '<':   // 栈顶元素优先权低
 87                       OPTR.push(c);  
 88                       c=getchar();
 89                       break;
 90             case '=':   // 脱括号并接收下一字符
 91                       OPTR.pop();   
 92                       c=getchar();
 93                       break;
 94             case '>':   // 退栈并将运算结果入栈
 95                       theta=OPTR.top();
 96                       OPTR.pop();
 97                       a=OPND.top();
 98                       OPND.pop();
 99                       b=OPND.top();  
100                       OPND.pop();                      
101                       OPND.push(Operate(b, theta, a)); 
102                       break;
103          } // switch
104       }           
105    }
106 
107    return OPND.top();
108 } // EvaluateExpression
109 
110 int main()
111 {
112     int t;
113     
114     scanf("%d",&t);
115     while(t--)
116     {
117     printf("%.2f\n",EvaluateExpression());
118     } 
119  return 0;
120 }