NYOJ - 郁闷的C小加（二）

描述

聪明的你帮助C小加解决了中缀表达式到后缀表达式的转换（详情请参考“郁闷的C小加（一）”），C小加很高兴。但C小加是个爱思考的人，他又想通过这种方法计算一个表达式的值。即先把表达式转换为后缀表达式，再求值。这时又要考虑操作数是小数和多位数的情况。

输入

第一行输入一个整数T，共有T组测试数据（T<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数并且小于1000000。
数据保证除数不会为0。

输出

对于每组测试数据输出结果包括两行，先输出转换后的后缀表达式，再输出计算结果，结果保留两位小数。两组测试数据之间用一个空行隔开。

样例输入

2

1+2=

(19+21)*3-4/5=

样例输出

12+=

3.00

1921+3*45/-=

119.20

#include <iostream>
#include <string>
#include <stack>
#include <iomanip>using namespace std;int cmp(char ch)
{switch(ch){case '+':case '-': return 1;case '*':case '/': return 2;default : return 0;}
}
void change(string &s1, string &s2)
{stack < char> s;int i = 0;s.push('#');while(i < s1.size()-1){if(s1[i] == '('){s.push(s1[i++]);}else if(s1[i] == ')'){while(s.top() != '('){s2 += s.top();s2 += ' ';s.pop();}s.pop();i++;}else if(s1[i] == '+'||s1[i] == '-'||s1[i] == '*'||s1[i] == '/'){while(cmp(s.top()) >= cmp(s1[i])){s2 += s.top();s2 += ' ';s.pop();}s.push(s1[i++]);}else{while('0' <= s1[i]&&s1[i] <= '9'||s1[i] == '.'){s2 += s1[i++];}s2 += ' ';}}while(s.top() != '#'){s2 += s.top();s2 += ' ';s.pop();}
}
double value(string s2)
{stack < double> s;int i = 0;double x = 0, y = 0;while(i < s2.size()){if(s2[i] == ' '){i++;continue;}switch(s2[i]){case '+': x = s.top(); s.pop(); x += s.top(); s.pop(); i++; break;case '-': x = s.top(); s.pop(); x =s.top()-x; s.pop(); i++; break;case '*': x = s.top(); s.pop(); x *= s.top(); s.pop(); i++; break;case '/': x = s.top(); s.pop(); x =s.top()/x; s.pop(); i++; break;default :{x = 0;while('0' <= s2[i]&&s2[i] <= '9'){x = x*10 + s2[i]-'0';i++;}if(s2[i] == '.'){double k = 10.0;y = 0;i++;while('0' <= s2[i]&&s2[i] <= '9'){y += (s2[i]-'0')/k;k *= 10;i++;}x += y;}}}s.push(x);}return s.top();
}
int main(int argc, char const *argv[])
{int n;string s1,s2;cin >> n;while(n--){cin >> s1;s2 = "";change(s1,s2);for(int i = 0; i < s2.size(); i++){if(s2[i] != ' '){cout<<s2[i];}}cout<<'='<<endl;cout<<fixed<<setprecision(2)<<value(s2)<<'\n'<<endl;}return 0;
}