题解 P1175 【表达式的转换】
用数组模拟了栈，学栈的同学看过来！！对新手超级友好哦~~
看了那么多大佬的题解，本蒟蒻觉得不是非常好懂，于是决定发一篇便于理解的题解，
（这个题有一个巨坑的地方，让RE了好几次——不能用gets（）！！what ？？）读入时用scanf就ac了，数组其实不用开那么大，我只是为了保险起见而已。。。。。
以下是转换的思路：
⑴ 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
⑵ 从左至右扫描中缀表达式；
⑶ 遇到操作数时，将其压s2；
⑷ 遇到运算符时，比较其与s1栈顶运算符的优先级：
① 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
② 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
③ 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到①与s1中新的栈顶运算符相比较；
⑸ 遇到括号时：
① 如果是左括号“(”，则直接压入s1；
② 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
⑹ 重复步骤⑵至⑸，直到表达式的最右边；
⑺ 将s1中剩余的运算符依次弹出并压入s2；
⑻ 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
然后就可以按照后缀表达式来计算了，（注意每一步都要输出，其中有最后输出空格和回车是无所谓的，强迫症把它们都去了防止不过，其实不去就好，省的弄错，嘻嘻~）不会的可以参考后缀表达式
话不多说上代码：：
#include<bits/stdc++.h>
using namespace std;
char s1[100010],s2[100010],s3[100010],a[100010];
long long top2,top1,p;
long long js[100010],topjs;
int lev(char n)
{
if(n=='+'||n=='-') return 1;
if(n=='*'||n=='/') return 2;
if(n=='^') return 3;
return 0;
}
void print()
{
for(int i=1;i<=topjs;i++)
{
cout<<js[i]<<" ";
}
for(int i=p+1;i<=top2;i++)
{
cout<<s2[i];
if(i!=top2)
cout<<" ";
}
if(p!=top2)
cout<<endl;
}
int main()
{
long long n;
scanf("%s",a);
n=strlen(a);//不能用gets（）
for(int i=0;i<n;i++)
{
if(a[i]>='0'&&a[i]<='9')
{
s2[++top2]=a[i];
}
else
{
if(a[i]=='(')
{
s1[++top1]=a[i];
continue;
}
if(s1[top1]=='('||top1==0)
{
s1[++top1]=a[i];
continue;
}
if(lev(s1[top1])>=lev(a[i])&&a[i]!=')')
{
s2[++top2]=s1[top1--];
while(lev(s1[top1])>=lev(a[i]))
{
s2[++top2]=s1[top1--];
}
s1[++top1]=a[i];
continue;
}
if(lev(s1[top1])<lev(a[i])&&a[i]!=')')
{
s1[++top1]=a[i];
continue;
}
if(a[i]==')')
{
while(s1[top1]!='(')
{
s2[++top2]=s1[top1--];
}
--top1;
continue;
}
}
}
/*for(int i=top1;i>=1;i--)
{
cout<<s1[i]<<endl;
}*/
while(top1>0)
{
s2[++top2]=s1[top1--];
} //到此为止前缀表达式已经转成了后缀表达式，并存在了s2数组中
for(int i=1;i<=top2;i++)
{
cout<<s2[i]<<" ";
}
cout<<endl;//先输出一遍
for(int i=1;i<=top2;i++)
{ p=i;
if(s2[i]>='0'&&s2[i]<='9')
{
js[++topjs]=s2[i]-'0';
}
else
{
if(s2[i]=='+')
{
long long y=js[topjs];
long long x=js[--topjs];
long long ans=x+y;
js[topjs]=ans;
}
if(s2[i]=='-')
{
long long y=js[topjs];
long long x=js[--topjs];
long long ans=x-y;
js[topjs]=ans;
}
if(s2[i]=='*')
{
long long y=js[topjs];
long long x=js[--topjs];
long long ans=x*y;
js[topjs]=ans;
}
if(s2[i]=='/')
{
long long y=js[topjs];
long long x=js[--topjs];
long long ans=x/y;
js[topjs]=ans;
}
if(s2[i]=='^')
{
long long y=js[topjs];
long long x=js[--topjs];
long long ans=pow(x,y);
js[topjs]=ans;
}
print();
}
}
return 0;
}看在纯手打的份上，给我赞一个吧~~求过