题目链接：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
思路：用栈模拟数的四则运算；初始化各种运算符之间的优先级；
代码如下：
#include "stdio.h"
#include "string.h"
#include "stack"
using namespace std; #define N 2005 char str[N];
int OPS[];
char table[][]={">><<<>>",">><<<>>",">>>><>>",">>>><>>","<<<<<=<",">>>>>>>","<<<<<<="};
//上面语句定义了操作符之间的优先级，从0~6依次为+-*/()=七种运算符 double Calculate(char ch,double x1,double x2)
{
if(ch=='+')
return x1+x2;
else if(ch=='-')
return x1-x2;
else if(ch=='*')
return x1*x2;
else if(ch=='/')
return x1/x2;
} int main()
{
int T;
int i,j;
int len;
memset(OPS,-,sizeof(OPS));
OPS['+'] = ;
OPS['-'] = ;
OPS['*'] = ;
OPS['/'] = ;
OPS['('] = ;
OPS[')'] = ;
OPS['='] = ;
scanf("%d",&T);
getchar();
while(T--)
{
scanf("%s",str+);
str[] = '=';
stack<double> q; //操作数栈
stack<char> t; //操作符栈
len = strlen(str);
for(i=; i<len; )
{
if(OPS[str[i]]==-) //若当前字符不为运算符，将这个数字读下来加入操作数栈(double类型)
{
int wei=;
bool flag = true;
double temp=;
for(j=i; OPS[str[j]]==-; ++j)
{
if(str[j]=='.'){ flag = false; continue; }
temp = temp*+str[j]-'';
if(!flag) wei*=;
}
temp = temp/wei;
i = j;
q.push(temp);
}
else
{
if(t.empty()) //若操作符栈为空，直接将下一个操作符加入操作符队列
t.push(str[i++]);
else
{
char ch1 = t.top();
char ch2 = str[i];
if(table[OPS[ch1]][OPS[ch2]]=='>') //前一个操作符先执行，则先执行前一个操作符，再加入这个操作符
{
double x2 = q.top();
q.pop();
double x1 = q.top();
q.pop();
char ch = t.top();
t.pop();
double x = Calculate(ch,x1,x2); //运算这两个数
q.push(x);
}
else if(table[OPS[ch1]][OPS[ch2]]=='<') //前一个操作符后执行，则直接将当期这个操作如入栈
t.push(str[i++]);
else if(table[OPS[ch1]][OPS[ch2]]=='=') //'='的情况表示括号对，后者等号对，将这两个操作符都消去。
t.pop(), i++;
}
}
}
printf("%.2lf\n",q.top());
q.pop();
}
return ;
}