郁闷的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. ",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]==' '){ 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]=' '; suf_exp[m]=' '; 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 ",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 ",suf_exp,'='); printf("%.2lf ",S_nd.top()); S_nd.pop(); printf(" "); } return 0; } /* 5 1+((2+3)*4)-5= (19+21)*3-4/5= 9+(3-1)*3+10/2= */