郁闷的C小加（三）
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
- 聪明的你帮助C小加解决了中缀表达式到后缀表达式的转换（详情请参考“郁闷的C小加（一）”），C小加很高兴。但C小加是个爱思考的人，他又想通过这种方法计算一个表达式的值。即先把表达式转换为前缀和后缀表达式，再求值。这时又要考虑操作数是小数和多位数的情况。
- 输入
- 第一行输入一个整数T，共有T组测试数据（T<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数并且小于1000000。
数据保证除数不会为0。 - 输出
- 对于每组测试数据输出结果包括三行，先输出转换后的前缀和后缀表达式，再输出计算结果，结果保留两位小数。
- 样例输入
2
1+2=
(19+21)*3-4/5=- 样例输出
+ 1 2 =
1 2 + =
3.00
- * + 19 21 3 / 4 5 =
19 21 + 3 * 4 5 / - =
119.20#include<bits/stdc++.h>
using namespace std;
stack<char>S_tr;//用作后缀表达式运算符存储和前缀表达式存储数字
stack<double>S_nd;//用作存储操作数
stack<char>S_pre_optr;//用作前缀表达式计算中运算符存储
stack<string>S_pre_exp;//用以存放前缀表达式
char suf_exp[1200],suf_exp_i[1200],pre_str[1200];
int m,k,pos;
char suf_compare(char op1,char op2){//转后缀表达式时，比较优先级
// printf(".%c%c.\n",op1,op2);
if(op1=='+'||op1=='-'){
if( op2=='(' || op2=='*' || op2=='/')
return '<';
else return '>';
}
if(op1=='*'||op1=='/'){
if(op2=='(')
return '<';
else return '>';
}
if(op1=='='||op1=='('){
if((op1=='='&&op2=='=')||(op1=='('&&op2==')')){
return '=';
}else{
return '<';
}
}
}
char pre_compare(char a,char b){//转前缀表达式时，比较优先级
if(a=='+'||a=='-'){
if(b=='('||b=='='){
return '>';
}else{
return '<';
}
}
if(a=='*'||a=='/'){
if(b==')'||b=='*'||b=='/'){
return '<';
}else{
return '>';
}
}
if(a==')'||a=='='){
if(a==')'&&b=='('||a=='='&&b=='='){
return '=';
}else{
return '<';
}
}
}
void suf_solve(char a,char b){//求后缀表达式时，当栈顶>当前运算符优先级
if(suf_compare(a,b)=='>'){
suf_exp[m++]=a;//后缀表达式中出现的所有的运算符都在这里放入数组，所以在此加空格
suf_exp[m++]=' ';
suf_exp_i[k++]=a;
S_tr.pop();
suf_solve(S_tr.top(),b);
}else if(suf_compare(a,b)=='<'){
S_tr.push(b);
return;
}else{
S_tr.pop();
return ;
}
}
void pre_solve(char a,char b){//求前缀表达式时，当栈顶>当前运算符优先级
if(pre_compare(a,b)=='>'){
string ts="";
ts+=a;
S_pre_exp.push(ts);
S_pre_optr.pop();
pre_solve(S_pre_optr.top(),b);
}
if(pre_compare(a,b)=='<'){
S_pre_optr.push(b);
return ;
}
if(pre_compare(a,b)=='='){
S_pre_optr.pop();
return;
}
}
double get_num(int po,int len){ //提取数字
double ret=0;
int temp=0,tmp=1,integ=-1;
for(int i=po;i<len;i++){
if(suf_exp[i]==' '||suf_exp[i]=='\0'){
pos=i;
break;
}
if(suf_exp[i]=='.'){
integ=temp;
temp=0;
tmp=1;
continue;
}else{
int tm=suf_exp[i]-'0';
temp*=10;
temp+=tm;
tmp*=10;
}
}
if(integ!=-1)
ret=integ*1.0+temp*1.0/tmp;
else ret=temp*1.0;
return ret;
}
int main(){
int t;
char mid_exp[1200];
scanf("%d",&t);
while(t--){
while(!S_tr.empty()){
S_tr.pop();
}
while(!S_nd.empty())
S_nd.pop();
S_tr.push('=');
m=0;
k=0;
scanf("%s",mid_exp);
int len=strlen(mid_exp);
bool flag=0;
for(int i=0;i<len;i++){
if(mid_exp[i]>='0'&&mid_exp[i]<='9'||mid_exp[i]=='.'){
suf_exp[m++]=mid_exp[i];
suf_exp_i[k++]=mid_exp[i];
flag=1;
}
else{
if(flag==1){
suf_exp[m++]=' ';
flag=0;
}
switch(suf_compare(S_tr.top(),mid_exp[i])){
case '<': S_tr.push(mid_exp[i]);break;
case '>': suf_solve(S_tr.top(),mid_exp[i]);break;
case '=': S_tr.pop();break;
}
}
}
suf_exp_i[k]='\0';
suf_exp[m]='\0';
m++;
strcpy(pre_str+1,mid_exp);
while(!S_tr.empty())
S_tr.pop();
while(!S_pre_exp.empty())
S_pre_exp.pop();
string pre_;
bool flg=0;
pre_str[0]='=';
S_pre_optr.push('=');
for(int i=len-1;i>=0;i--){
if(pre_str[i]>='0'&&pre_str[i]<='9'||pre_str[i]=='.'){
flg=1;
S_tr.push(pre_str[i]);
}else{
if(flg==1){
flg=0;
pre_="";
while(!S_tr.empty()){
pre_+=S_tr.top();
S_tr.pop();
}
S_pre_exp.push(pre_);
}
switch(pre_compare(S_pre_optr.top(),pre_str[i])){
case '<' :S_pre_optr.push(pre_str[i]);break;
case '>' :pre_solve(S_pre_optr.top(),pre_str[i]);break;
case '=' :S_pre_optr.pop(); break;
default : break;
}
}
}
while(!S_pre_exp.empty()){
cout<<S_pre_exp.top()<<" ";
S_pre_exp.pop();
}printf("=");
cout<<endl;
double a,b;
for(int i=0;i<m;i++){
if(suf_exp[i]>='0'&&suf_exp[i]<='9'){
S_nd.push(get_num(i,m));
i=pos;
}else{
switch(suf_exp[i]){ //printf("%.3lf %.3lf\n",a,b);
case '+': b=S_nd.top(),S_nd.pop();a=S_nd.top(),S_nd.pop();S_nd.push(a+b);break;
case '-': b=S_nd.top(),S_nd.pop();a=S_nd.top(),S_nd.pop();S_nd.push(a-b);break;
case '*': b=S_nd.top(),S_nd.pop();a=S_nd.top(),S_nd.pop();S_nd.push(a*b);break;
case '/': b=S_nd.top(),S_nd.pop();a=S_nd.top(),S_nd.pop();S_nd.push(a/b);break;
default : break;
}
}
}
printf("%s%c\n",suf_exp,'=');
printf("%.2lf\n",S_nd.top());
S_nd.pop();
printf("\n");
}
return 0;
}
/*
5
1+((2+3)*4)-5= (19+21)*3-4/5=
9+(3-1)*3+10/2= */