数据结构--栈的应用(表达式求值 nyoj 35)

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=35

题目：

　　　　　　　　　　　　　　　　　　　　表达式求值
　　　　　　　　　　　　　　　　时间限制：3000 ms | 内存限制：65535 KB
描述
　　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 "string.h"
 3 #include "stack"
 4 using namespace std;
 5 
 6 #define N 2005
 7 
 8 char str[N];
 9 int OPS[256];
10 char table[8][8]={">><<<>>",">><<<>>",">>>><>>",">>>><>>","<<<<<=<",">>>>>>>","<<<<<<="};
11 //上面语句定义了操作符之间的优先级，从0~6依次为+-*/()=七种运算符
12 
13 double Calculate(char ch,double x1,double x2)  
14 {
15     if(ch=='+')
16         return x1+x2;
17     else if(ch=='-')
18         return x1-x2;
19     else if(ch=='*')
20         return x1*x2;
21     else if(ch=='/')
22         return x1/x2;
23 }
24 
25 int main()
26 {
27     int T;
28     int i,j;
29     int len;
30     memset(OPS,-1,sizeof(OPS));
31     OPS['+'] = 0;
32     OPS['-'] = 1;
33     OPS['*'] = 2;
34     OPS['/'] = 3;
35     OPS['('] = 4;
36     OPS[')'] = 5;
37     OPS['='] = 6;
38     scanf("%d",&T);
39     getchar();
40     while(T--)
41     {
42         scanf("%s",str+1);
43         str[0] = '=';
44         stack<double> q;  //操作数栈
45         stack<char> t;  //操作符栈
46         len = strlen(str);
47         for(i=0; i<len; )
48         {
49             if(OPS[str[i]]==-1)  //若当前字符不为运算符，将这个数字读下来加入操作数栈(double类型)
50             {
51                 int wei=1;
52                 bool flag = true;
53                 double temp=0;
54                 for(j=i; OPS[str[j]]==-1; ++j)
55                 {
56                     if(str[j]=='.'){ flag = false; continue; }
57                     temp = temp*10+str[j]-'0';
58                     if(!flag) wei*=10;
59                 }
60                 temp = temp/wei;
61                 i = j;
62                 q.push(temp);
63             }
64             else
65             {
66                 if(t.empty())  //若操作符栈为空，直接将下一个操作符加入操作符队列
67                     t.push(str[i++]);
68                 else
69                 {
70                     char ch1 = t.top();
71                     char ch2 = str[i];
72                     if(table[OPS[ch1]][OPS[ch2]]=='>')  //前一个操作符先执行，则先执行前一个操作符，再加入这个操作符
73                     {
74                         double x2 = q.top(); 
75                         q.pop();
76                         double x1 = q.top(); 
77                         q.pop();
78                         char ch = t.top(); 
79                         t.pop();
80                         double x = Calculate(ch,x1,x2); //运算这两个数
81                         q.push(x);
82                     }
83                     else if(table[OPS[ch1]][OPS[ch2]]=='<')  //前一个操作符后执行，则直接将当期这个操作如入栈
84                         t.push(str[i++]);
85                     else if(table[OPS[ch1]][OPS[ch2]]=='=') //'='的情况表示括号对，后者等号对，将这两个操作符都消去。
86                         t.pop(), i++;
87                 }
88             }
89         }
90         printf("%.2lf
",q.top());
91         q.pop();
92     }
93     return 0;
94 }