题解 P1175 【表达式的转换】
这个题其实是个很麻烦的栈，坑点不多，但不坑点也很难搞。大体思路其实都懂，中序转后序，然后后序再慢慢算。第一部分我其实没怎么看懂楼下大佬，就简单讲讲吧。
第一部分：
由于保证输入数据数字是单位数所以可以用字符数组。
设有一个中序式：a+b*(c+d^e)/f-g
我们的原则是：如果栈顶符号优先级>=此时的符号，就弹出，（优先级最低
我们的栈，主要是用来储存符号的，为了方便，以下所指的输出，均为放入结果字符数组中。
首先读入a，可以直接输出。
其次读入+，放入栈（栈内：+)
在读入b，直接输出。
再读入，放入栈内，因为+优先级<（栈内：+*）
读入(，放入栈中，不进行任何操作，栈内：（+*（）
读入c，直接输出
读入+，放入栈内（栈内：+*（+）
读入d，直接输出
读入^,放入栈内(注意：到目前为止，我们还未弹出栈内任何元素）（栈内：+*（^))
读入e，输出
读入（，原则：一直弹顺便输出，弹到（，(不输出 栈内：+*
后面如前面所示，最后将栈内所有元素，逆序输出（即由top到1)
好的，一直到这，我的想法都和楼下大佬一样，但是在计算过程中，我的会有所差异。
第二部分：
这时候，我们还需要一个栈，但不是储存符号了，而是运算结果（注意，并非输入的数据，而是结果）
如样例，我们的后序式是：8 3 2 6 * + 5 / - 4 + ，我们的储存方式是字符。
栈内一直读到第4位，已经变成了：8 3 2 6
但是到了*，我们需要对后两位进行运算，于是栈内变成了：8 3 12
请读者观察，我们需要输出时，一定是在运算时，对不对？很明显，我们此时进行了运算。那么输出的内容，首先，应当是栈内的内容，然后6和*已经运算完了，不需要输出，那么应该跳过这两个，然后把原先式子输出出来。那么这个2，并非意思跳过这两个，而是在6所跳的基础上，再跳两个。但是，如果这个位置需要多次跳跃，前面的跳跃格数已经不能满足他了，就必须自增2，那么式子，留给作者思考（其实程序会有qaq），那么如果他已经过去了这些东西，就需要从后面再计算了（此处表述可能不是太清楚），直到到了最后面。可能这样看不太明晰，那么画一个图可能就明白了。
输出必要性：1 1 1 1 1 1 1
运算完一遍后，一个可能的结果：
0 0 0 1 1 1 1
那么需要把栈内的输出一边（因为不可能有符号了），然后再把下面的输出一遍，即把必要性为1的输出一遍。
一直到全部为零为止。
表述不清，请见谅。 AC代码：
#include <iostream>
#include <cmath>
using namespace std;
char out[200],stac[200],ch;
int top,outsize,skip[200];
struct st{
int num,mem;
}sta[200];
int main(){
while(cin >> ch)
{
if(ch<='9'&&ch>='0')//num
{
outsize++;
out[outsize]=ch;
}
if(ch=='+'||ch=='-')//+||-
{
while(top>0&&stac[top]!='(')
{
outsize++;
out[outsize]=stac[top];
top--;
}
top++;
stac[top]=ch;
}
if(ch=='*'||ch=='/')
{
while(top>0&&stac[top]!='('&&stac[top]!='+'&&stac[top]!='-')//*||/
{
outsize++;
out[outsize]=stac[top];
top--;
}
top++;
stac[top]=ch;
}
if(ch=='^')
{
while(top>0&&stac[top]=='^')
{
outsize++;
out[outsize]=stac[top];
top--;
}
top++;
stac[top]=ch;
}
if(ch=='(')
{
top++;
stac[top]=ch;
}
if(ch==')')
{
while(top>0&&stac[top]!='(')
{
outsize++;
out[outsize]=stac[top];
top--;
}
top--;
}
}
while(top>0)
{
outsize++;
out[outsize]=stac[top];
top--;
}
for(int i=1;i<=outsize;i++)
{
cout << out[i] << " ";
skip[i]=1;
}
cout << endl;
int st=1;
top=0;
while(st<=outsize)
{
if(out[st]<='9'&&out[st]>='0')
{
top++;
sta[top].mem=out[st]-'0';
sta[top].num=st;
}
if(out[st]=='+')
{
sta[top-1].mem+=sta[top].mem;
if(skip[top-1]-skip[top]>=2)
{
skip[top-1]+=2;
}
else
{
skip[top-1]=skip[top]+2;
}
top--;
for(int i=1;i<=top;i++)
{
cout << sta[i].mem << " ";
}
int j;
for(j=st+1;j<=outsize;j++)
{
cout << out[j] << " ";
}
cout << endl;
}
if(out[st]=='-')
{
sta[top-1].mem-=sta[top].mem;
if(skip[top-1]-skip[top]>=2)
{
skip[top-1]+=2;
}
else
{
skip[top-1]=skip[top]+2;
}
top--;
for(int i=1;i<=top;i++)
{
cout << sta[i].mem << " ";
}
int j;
for(j=st+1;j<=outsize;j++)
{
cout << out[j] << " ";
}
cout << endl;
}
if(out[st]=='*')
{
sta[top-1].mem*=sta[top].mem;
if(skip[top-1]-skip[top]>=2)
{
skip[top-1]+=2;
}
else
{
skip[top-1]=skip[top]+2;
}
top--;
for(int i=1;i<=top;i++)
{
cout << sta[i].mem << " ";
}
int j;
for(j=st+1;j<=outsize;j++)
{
cout << out[j] << " ";
}
cout << endl;
}
if(out[st]=='/')
{
sta[top-1].mem/=sta[top].mem;
if(skip[top-1]-skip[top]>=2)
{
skip[top-1]+=2;
}
else
{
skip[top-1]=skip[top]+2;
}
top--;
for(int i=1;i<=top;i++)
{
cout << sta[i].mem << " ";
}
int j;
for(j=st+1;j<=outsize;j++)
{
cout << out[j] << " ";
}
cout << endl;
}
if(out[st]=='^')
{
sta[top-1].mem=pow(sta[top-1].mem,sta[top].mem);
if(skip[top-1]-skip[top]>=2)
{
skip[top-1]+=2;
}
else
{
skip[top-1]=skip[top]+2;
}
top--;
for(int i=1;i<=top;i++)
{
cout << sta[i].mem << " ";
}
int j;
for(j=st+1;j<=outsize;j++)
{
cout << out[j] << " ";
}
cout << endl;
}
st++;
}
return 0;
}码量蛮大的，要有耐心