题解 P1175 【表达式的转换】
因为要输出计算步骤，所以采用数组模拟栈，便于输出。
按照题意先将中缀表达式转换成后缀表达式，然后再计算：
⑴ 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
⑵ 从左至右扫描中缀表达式；
⑶ 遇到操作数时，将其压s2；
⑷ 遇到运算符时，需考虑以下多种情况：
① 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
② 否则，比较其与s1栈顶运算符的优先级，若优先级比栈顶运算符的高，也将运算符压入s1；
③ 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到①与s1中新的栈顶运算符相比较；
⑸ 遇到括号时：
① 如果是左括号“(”，则直接压入s1；
② 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
⑹ 重复步骤⑵至⑸，直到表达式的最右边；
⑺ 将s1中剩余的运算符依次弹出并压入s2；
⑻ 依次输出数组s2中的元素，即为中缀表达式所对应的后缀表达式
转换之后的后缀表达式保存在数组s2中，从头开始遍历数组s2，遇到数字压入栈s3;遇到运算符时则弹出位于s3栈顶的两个数字用该运算符进行运算，并将计算结果压入s3，然后输出s3中的数字和s2中当前遍历位置以后的字符，即输出当前这一步的运算过程。
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
char str[101];
char s1[101];
char s2[101];
long long s3[101];
int n,len,top1=0,top2=0;
int lev(char a)
{
if(a=='+'||a=='-') return 1;
if(a=='*'||a=='/') return 2;
if(a=='^') return 3;
return 0;
}
long long ksm(long long s,long long t)//快速幂
{
long long res=1;
while(t)
{
if(t&1) res*=s;
s*=s;
t>>=1;
}
return res;
}
void cvt(char s[101])//将中缀表达式转换成后缀表达式
{
for(int i=0;i<n;i++)
{
if('0'<=s[i]&&s[i]<='9')
s2[++top2]=s[i];
else if(s[i]=='(')
s1[++top1]=s[i];
else if(s[i]==')')
{
while(s1[top1]!='(') s2[++top2]=s1[top1--];
top1--;
}
else if(top1==0||s1[top1]=='('||(lev(s[i])>lev(s1[top1])))
s1[++top1]=s[i];
else //else if(lev(s[i])<=lev(s1[top1]))
{
s2[++top2]=s1[top1--];
i=i-1;
}
}
while(top1>0)
s2[++top2]=s1[top1--];
len=top2;
for(int j=1;j<=len;j++)//后缀表达式保存在s2中，包括运算符和数字，类型为char
cout<<s2[j]<<" ";
cout<<endl;
}
/*从头开始遍历数组s2，遇到数字压入栈s3;
遇到运算符弹出s3栈顶两个数字进行运算，然后输出s3中剩余数字和s2中当前遍历位置以后的字符*/
void js(char s[101])
{
int i=1,top=0;
while(i<=len)
{
switch(s[i])
{
case '+':top--;s3[top]+=s3[top+1];
for(int j=1;j<=top;j++) cout<<s3[j]<<" ";
for(int k=i+1;k<=len;k++)
cout<<s2[k]<<" ";
cout<<endl;
break;
case '-':top--;s3[top]-=s3[top+1];
for(int j=1;j<=top;j++) cout<<s3[j]<<" ";
for(int k=i+1;k<=len;k++)
cout<<s2[k]<<" ";
cout<<endl;
break;
case '*':top--;s3[top]*=s3[top+1];
for(int j=1;j<=top;j++) cout<<s3[j]<<" ";
for(int k=i+1;k<=len;k++)
cout<<s2[k]<<" ";
cout<<endl;
break;
case '/':top--;s3[top]/=s3[top+1];
for(int j=1;j<=top;j++) cout<<s3[j]<<" ";
for(int k=i+1;k<=len;k++)
cout<<s2[k]<<" ";
cout<<endl;
break;
case '^':top--;s3[top]=ksm(s3[top],s3[top+1]);
for(int j=1;j<=top;j++) cout<<s3[j]<<" ";
for(int k=i+1;k<=len;k++)
cout<<s2[k]<<" ";
cout<<endl;
break;
default:top++;s3[top]=s[i]-'0';//字符转换成数字
break;
}
i++;
}
}
int main()
{
cin>>str;
n=strlen(str);
cvt(str);
js(s2);
return 0;
}