题解 P1175 【表达式的转换】
简单来说就是中缀转后缀再一步步求值的过程， 具体方法见李煜东《算法竞赛进阶指南》P48,49，这上面讲得很清楚。（这的确是一本好书），以下是本蒟蒻的程序
#include<bits/stdc++.h>
int sz(char x){
return (x>='0'&&x<='9');
}
using namespace std;
int g[110],f[110];//g数组记录上一次计算结果，用于拓展f数组； f数组记录本轮的答案用于输出。
char z[110]; //z数组用于后缀表达式转化时的输出
char tr[110];//玄学数组tr 存储第一次的后缀表达式
map<char,int> mm;
int main(){
mm['^']=3;mm['*']=2;mm['/']=2;mm['+']=1;
mm['-']=1;mm['(']=mm[')']=-100;//用map保存符号优先级
int l,s=0,ss=0,i,ans=0,j,sum=0;
string st,st1;
cin>>st1;
st='0';st+=st1;l=st.size();
//字符串默认从零开始，所以我们在零号位添个零
（个人习惯）
//中缀表达式---->后缀表达式
for (int i=1;i<=l;i++)
{ //我是一个只会用if的蒟蒻*1
if (sz(st[i])) ss++,cout<<st[i]<<" ",sum++,tr[sum]=st[i];else
{
if (st[i]=='(') s++,z[s]=st[i];else
//处理左括号
if (st[i]==')')
{
while (z[s]!='(') cout<<z[s]<<" ",sum++,tr[sum]=z[s],s--;
s--; //处理右括号
} else
{ //处理运算符
while (mm[z[s]]>=mm[st[i]]&&s>=1) //比较优先级
cout<<z[s]<<" ",sum++,tr[sum]=z[s],s--;
s++;z[s]=st[i];
}
}
} //用tr记录输出结果
cout<<endl;
//*********************************************
int big=200000000;
for (i=1;i<=sum;i++)
{ //我是一个只会用if的蒟蒻*2
if (sz(tr[i])) g[i]=int(tr[i])-48;else
if (tr[i]=='+') g[i]=big+1;else
if (tr[i]=='-') g[i]=big+2;else
if (tr[i]=='*') g[i]=big+3;else
if (tr[i]=='/') g[i]=big+4;else
if (tr[i]=='^') g[i]=big+5;
// 后缀表达式一定不含括号(这就是它优美的原因)
} //将运算符用 200000000+x表示，不太保险，但亲测不会冲突。
while (sum>1)//不解释
{
int t=0;//标记
f[1]=g[1];f[2]=g[2];//前两位预处理
for (i=3;i<=l;i++)
{
int x=f[i-1];int y=f[i-2];
if (g[i]==big+1) ans=x+y,t=1;else // 加法
if (g[i]==big+2) ans=y-x,t=1;else // 减法
if (g[i]==big+3) ans=x*y,t=1;else // 乘法
if (g[i]==big+4) ans=y/x,t=1;else // 除法
if (g[i]==big+5) ans=pow(y,x),t=1;else // 乘方
f[i]=g[i]; // 非运算符则照抄
if (t==1) break;
}
f[i-2]=ans;
//f[i-2]与f[i-1]的运算结果覆盖在f[i-2]上
for (j=i+1;j<=sum;j++) f[j-2]=g[j];
//将剩下的数照抄下来
sum-=2;//一次运算减少一个数和一个运算符
for (j=1;j<=sum;j++)
{ //我是一个只会用if的蒟蒻*3
if (f[j]==big+1) cout<<"+ ";else
if (f[j]==big+2) cout<<"- ";else
if (f[j]==big+3) cout<<"* ";else
if (f[j]==big+4) cout<<"/ ";else
if (f[j]==big+5) cout<<"^ ";else
cout<<f[j]<<" ";
g[j]=f[j];
//记录本轮答案用于下轮拓展
}//每轮输出，将 200000000+x转回运算符
cout<<endl;
}
return 0;
}