中缀表达式转后缀表达式详细思路及代码实现

什么是中缀表达式？

中缀表达式是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（eg:3+4、3+4*2、8+(17-6*2)….）。

为什么要中缀表达式转后缀表达式？

但是中缀表达式不易被计算机处理。我们在计算一个式子（通常为中缀表达式）时，需要将中缀表达式转化为后缀表达式。

 什么是后缀表达式？

那么后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不再考虑运算符的优先规则)。一般用栈来模拟。

怎么把中缀表达式转成后缀表达式呢？

举一个简单的栗子：

(3+4)×5-2

画成树大概是这样的：

所以后缀表达式为：

3  4  +  5  ×  2  -

以下是转换的思路：

1．初始化两个字符型数组模拟栈：字符存入栈s1和储存中间结果的栈s2；

2．从左至右扫描中缀表达式；

3．遇到操作数时，将其压s2；

4．遇到运算符时，比较其与s1栈顶运算符的优先级：

如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

否则，若优先级比栈顶运算符的高，也将运算符压入s1；

否则，将s1栈顶的运算符弹出并压入到s2中，再次转到①与s1中新的栈顶运算符相比较；

5．遇到括号时：

如果是左括号“(”，则直接压入s1；

如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；

6．重复步骤2至5，直到表达式的最右边；

7．将s1中剩余的运算符依次弹出并压入s2；

8．依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

然后就可以按照后缀表达式来计算了。

一定要注意取出元素的计算顺序！先取出的数为X数(X为减/除/加/乘)，后取出的数为被X数！

 代码（有详细注释）：

#include<bits/stdc++.h>//万能头文件
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//加速语句
typedef long long ll;
const int N=1e5+10;
char s1[N],s2[N],s[N];
ll top1,top2,p,js[N],topis;
 
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<=topis;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()
{
   cin>>s;
   for(int i=0;i<strlen(s);i++)
   {
       if(s[i]<='9'&&s[i]>='0')
       {
           s2[++top2]=s[i];
       }
       else
       {
           if(s[i]=='(')
           {
               s1[++top1]=s[i];
               continue;
           }
           if(s1[top1]=='('||top1==0)
           {
               s1[++top1]=s[i];
               continue;
           }
           if(lev(s1[top1])>=lev(s[i])&&s[i]!=')')//当进来的不是右括号，且进来的符号优先级没有s1的栈顶符号优先级高
            //这个时候需要将s1的栈顶元素给到s2中
           {
               s2[++top2]=s1[top1--];
               while(lev(s1[top1])>=lev(s[i]))//若优先级任然没有要进来的符号优先级高，持续的给到s2中
               {
                   s2[++top2]=s1[top1--];
               }
               //循环结束后，要进来的符号优先级没有s1的栈顶符号优先级高，则可以存入s1中
               s1[++top1]=s[i];
               continue;
           }
           if(lev(s1[top1])<lev(s[i])&&s[i]!=')')
           {
               s1[++top1]=s[i];
           }
           if(s[i]==')')//遇到了 ' ) '
           {
               while(s1[top1]!='(')//将s1中的符号依次给到s2中，直到遇到 ' ) '
               {
                   s2[++top2]=s1[top1--];
               }
               top1--;
               continue;
           }
       }
   }
   while(top1>0)//若s1还有符号的话，需要给到s2中
	{
		s2[++top2]=s1[top1--];
	}
	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[++topis]=s2[i]-'0';
        }
        else //为符号，对栈顶两个元素进行运算，并将结果存入栈顶
        {
            //注意先进栈的做运算的第一位数
            if(s2[i]=='+')
            {
                ll x=js[topis];
                ll y=js[--topis];
                ll ans=y+x;
                js[topis]=ans;
            }
            if(s2[i]=='-')
            {
                ll x=js[topis];
                ll y=js[--topis];
                ll ans=y-x;
                js[topis]=ans;
            }
            if(s2[i]=='*')
            {
                ll x=js[topis];
                ll y=js[--topis];
                ll ans=y*x;
                js[topis]=ans;
            }
            if(s2[i]=='/')
            {
                ll x=js[topis];
                ll y=js[--topis];
                ll ans=y/x;
                js[topis]=ans;
            }
            if(s2[i]=='^')
            {
                ll x=js[topis];
                ll y=js[--topis];
                ll ans=pow(y,x);
                js[topis]=ans;
            }
            print();//每一步都要打印
        }
    }
	return 0;
}
 

运行结果如下：