题目：给定一个中缀表达式，求其后缀表达式并输出结果；
以下是转换的思路：
⑴ 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
⑵ 从左至右扫描中缀表达式；
⑶ 遇到操作数时，将其压s2；
⑷ 遇到运算符时，比较其与s1栈顶运算符的优先级：
① 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
② 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
③ 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到①与s1中新的栈顶运算符相比较；
⑸ 遇到括号时：
① 如果是左括号“(”，则直接压入s1；
② 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
⑹ 重复步骤⑵至⑸，直到表达式的最右边；
⑺ 将s1中剩余的运算符依次弹出并压入s2；
⑻ 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
然后就可以按照后缀表达式来计算了，（注意每一步都要输出，其中有最后输出空格和回车是无所谓的，强迫症把它们都去了防止不过，其实不去就好，省的弄错，嘻嘻~）不会的可以参考后缀表达式
第一部分：中缀转后缀:
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
char a[100020],s1[10000],s2[100000];
long long n,m,top1,top2;
int lev(char ch)
{
if(ch==‘+‘ || ch==‘-‘)
return 1;
if(ch==‘*‘||ch==‘/‘)
return 2;
if(ch==‘^‘)
return 3;
return 0;
}
int main()
{
scanf("%s",a);
n=strlen(a);
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(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;
}
}
}
while(top1>0)
{
s2[++top2]=s1[top1--];
}
for(int i=1;i<=top2;i++)
cout<<s2[i]<<" ";
return 0;
}
第二部分：后缀表达式的求值：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[2000];
int s[2000],top;
int main()
{
scanf("%s",a);
int l=strlen(a);
for(int i=0;i<l-1;i++)
{
if(a[i]>=‘0‘&&a[i]<=‘9‘)
{
s[++top]=a[i]-‘0‘;
while(a[i+1]>=‘0‘&&a[i+1]<=‘9‘)
{
s[top]=s[top]*10+a[i+1]-‘0‘;
i++;
}
continue;
}
else
{
if(a[i]==‘.‘)
continue;
int y=s[top],x=s[--top];
if(a[i]==‘+‘)
{
s[top]=x+y;
continue;
}
if(a[i]==‘-‘)
{
s[top]=x-y;
continue;
}
if(a[i]==‘*‘)
{
s[top]=x*y;
continue;
}
if(a[i]==‘/‘)
{
s[top]=x/y;
continue;
}
}
}
printf("%d",s[top]);
return 0;
}
#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;
}
原文：https://www.cnblogs.com/little-cute-hjr/p/11450498.html