表达式计算

  1 #include<iostream>
  2 #include<string>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<iomanip>
  6 #include<stack>
  7 using namespace std;
  8 
  9 #define OK 0
 10 #define ERROR -1
 11 #define OVERFLOW -1
 12 #define OPSETSIZE 7
 13 typedef int Status;
 14 
 15 unsigned char Prior[7][7] = {     // 表3.1  算符间的优先关系
 16         ‘>‘,‘>‘,‘<‘,‘<‘,‘<‘,‘>‘,‘>‘,
 17       ‘>‘,‘>‘,‘<‘,‘<‘,‘<‘,‘>‘,‘>‘,
 18       ‘>‘,‘>‘,‘>‘,‘>‘,‘<‘,‘>‘,‘>‘,
 19       ‘>‘,‘>‘,‘>‘,‘>‘,‘<‘,‘>‘,‘>‘,    
 20       ‘<‘,‘<‘,‘<‘,‘<‘,‘<‘,‘=‘,‘ ‘,
 21       ‘>‘,‘>‘,‘>‘,‘>‘,‘ ‘,‘>‘,‘>‘,
 22       ‘<‘,‘<‘,‘<‘,‘<‘,‘<‘,‘ ‘,‘=‘
 23 };        
 24 float Operate(float a, unsigned char theta, float b);
 25 char OPSET[OPSETSIZE]={‘+‘ , ‘-‘ , ‘*‘ , ‘/‘ ,‘(‘ , ‘)‘ , ‘#‘};
 26 Status In(char Test,char* TestOp);
 27 char precede(char Aop, char Bop);
 28         
 29 float EvaluateExpression(string MyExp) {  // 算法3.4
 30    // 算术表达式求值的算符优先算法。
 31    // 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。
 32    stack <char> OPTR;    // 运算符栈，字符元素
 33    stack <double> OPND;   // 运算数栈，实数元素
 34    char TempData[20];
 35    float Data,a,b,r;
 36    char theta,Dr[2];
 37    char c;
 38    int i=0;
 39    OPTR.push(‘#‘);
 40    c=MyExp[0];
 41    strcpy(TempData,"\0");
 42    while (c!= ‘#‘ || OPTR.top()!= ‘#‘) {
 43       if (!In(c, OPSET)) {
 44            Dr[0]=c;
 45            Dr[1]=‘\0‘;
 46          strcat(TempData,Dr);
 47          c=MyExp[++i];
 48          if(In(c,OPSET)) {
 49             Data=(float)atof(TempData);
 50             OPND.push(Data);
 51             strcpy(TempData,"\0");
 52          }
 53       } else {   // 不是运算符则进栈
 54          switch (precede(OPTR.top(), c)) { 
 55             case ‘<‘:   // 栈顶元素优先权低
 56                  OPTR.push(c);  
 57                  c=MyExp[++i];
 58                  break;
 59             case ‘=‘:   // 脱括号并接收下一字符
 60                  OPTR.pop();   
 61                  c=MyExp[++i];
 62                  break;
 63             case ‘>‘:   // 退栈并将运算结果入栈
 64                 theta=OPTR.top();
 65                 OPTR.pop();
 66                 b=OPND.top();
 67                 OPND.pop();
 68                 a=OPND.top();
 69                 OPND.pop();
 70                 OPND.push(Operate(a, theta, b));
 71                 break;
 72          } // switch
 73       }
 74    } // while
 75    return OPND.top();
 76 } // EvaluateExpression
 77 
 78 float Operate(float a,unsigned char theta, float b) {
 79    switch(theta) {
 80       case ‘+‘: return a+b;
 81       case ‘-‘: return a-b;
 82       case ‘*‘: return a*b;
 83       case ‘/‘: return a/b;
 84       default : return 0;
 85    } 
 86 }    
 87 
 88 Status In(char Test,char* TestOp) {
 89    bool Find=false;
 90    for (int i=0; i< OPSETSIZE; i++) {
 91       if (Test == TestOp[i]) Find= true;
 92    }
 93    return Find;
 94 }
 95 
 96 
 97 int ReturnOpOrd(char op,char* TestOp) {
 98    int i;
 99    for(i=0; i< OPSETSIZE; i++) {
100       if (op == TestOp[i]) return i;
101    }
102    return 0;
103 }
104 
105 char precede(char Aop, char Bop) {
106    return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
107 }
108 
109 int main()
110 {
111     string Exp;
112     int t;
113     double result;
114     cin>>t;
115     while(t--){
116         cin>>Exp;
117         result=EvaluateExpression(Exp);
118         cout<<fixed<<setprecision(4)<<result<<endl;
119     }
120     return 0;
121 }