表达式求值

时间限制：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<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<stack>
 5 using namespace std;
 6 
 7 char a[1010];
 8 stack<char>s1;
 9 stack<float>s2;
10 
11 int fun(char x)
12 {
13     switch(x)
14     {
15         case '+':
16         case '-':return 1;
17         case '*':
18         case '/':return 2;
19         case '(':return 0;
20         default :return -1;
21     }
22 }
23 
24 float js(float x,float y,char z)
25 {
26     switch(z)
27         {
28             case '+':return y+x;
29             case '-':return y-x;
30             case '*':return y*x;
31             default :return y/x;
32         }
33 }
34 
35 int main()
36 {
37     int i,n,m,t;
38     float x,y,z;
39     s1.push('#');
40     scanf("%d",&t);
41     while(t--)
42     {
43         scanf("%s",a);
44         m=strlen(a)-1;
45         for(i=0;i<m;i++)
46         {
47             if(a[i]>='0'&&a[i]<='9'||a[i]=='.')
48             {
49                 sscanf(a+i,"%f%n",&x,&n);
50                 s2.push(x);
51                 i+=n-1;
52             }
53             
54             else if(a[i]=='(') s1.push(a[i]);
55 
56             else if(a[i]==')')
57             {
58                 while(s1.top()!='(')
59                 {
60                     z=s1.top();
61                     x=s2.top();s2.pop();
62                     y=s2.top();s2.pop();
63                     x=js(x,y,z);
64                     s2.push(x);
65                     s1.pop();
66                 }
67                 s1.pop();
68             }
69             else 
70             {
71                 while(fun(s1.top())>=fun(a[i]))
72                 {
73                     z=s1.top();
74                     x=s2.top();s2.pop();
75                     y=s2.top();s2.pop();
76                     x=js(x,y,z);
77                     s2.push(x);
78                     s1.pop();
79                 }
80                 s1.push(a[i]);
81             }
82         }
83 
84         while(s1.top()!='#')
85         {
86             z=s1.top();
87             x=s2.top();s2.pop();
88             y=s2.top();s2.pop();
89             x=js(x,y,z);
90             s2.push(x);
91             s1.pop();
92         }
93         printf("%.2f\n",s2.top());
94         s2.pop();
95     }
96     return 0;
97 }