Detailed idea and code implementation of infix expression to suffix expression

What is infix expression ？

Infix expression is a general expression of arithmetic or logic formula , Operators are in the middle of operands in the form of infixes （eg:3+4、3+4*2、8+(17-6*2)….）.

Why do you want infix expression to suffix expression ？

But infix expressions are not easy to be processed by computers . We are calculating an equation （ Usually infix expression ） when , You need to convert infix expression into suffix expression .

  What is a suffix expression ？

Then the suffix expression , Also known as reverse Polish , Does not contain brackets , The operator is placed after two operands , All calculations are in the order in which the operators appear , Strictly from left to right ( The precedence rules for operators are no longer considered ). Generally, stack is used to simulate .

How to convert infix expression into suffix expression ？

Take a simple chestnut ：

(3+4)×5-2

Draw a tree like this ：

So the suffix expression is ：

3  4  +  5  ×  2  -

The following is the idea of transformation ：

1． Initialize two character array simulation stacks ： Character storage stack s1 And a stack for storing intermediate results s2;

2． Scan infix expressions from left to right ;

3． When it comes to operands , Press it down s2;

4． When an operator is encountered , Compare it with s1 The priority of the top of stack operator ：

If s1 It's empty , Or stack top operator is left bracket “(”, This operator will be put on the stack directly ;

otherwise , If the priority is higher than the top of the stack operator , Also push operators into s1;

otherwise , take s1 The operator at the top of the stack pops up and pushes into s2 in , Turn again ① And s1 Compared with the new stack top operators in ;

5． When brackets are encountered ：

If it's left parenthesis “(”, Press in directly s1;

If it's right bracket “)”, Then it pops up in turn s1 The operator at the top of the stack , And press in s2, Until we meet the left bracket , This pair of parentheses is discarded ;

6． Repeat step 2 to 5, Up to the far right of the expression ;

7． take s1 The rest of the operators in the pop-up and press in s2;

8． Pop up one by one s2 And output , The reverse order of the result is the suffix expression corresponding to the infix expression

Then it can be calculated according to the suffix expression .

Be sure to pay attention to the calculation order of taking out elements ！ The number taken out first is X Count (X To reduce / except / Add / ride ), The number taken out after is By X Count ！

  Code （ There are detailed notes ）：

#include<bits/stdc++.h>// Universal header file 
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// Accelerated statement 
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++)// Currently being calculated 
    {
        cout<<js[i]<<' ';
    }
    for(int i=p+1;i<=top2;i++)// Not traversed later 
    {
        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]!=')')// When it comes in, it's not the right bracket , And the incoming symbol priority has no s1 The stack top symbol of has high priority 
            // At this time, we need to s1 The top element of the stack is given to s2 in 
           {
               s2[++top2]=s1[top1--];
               while(lev(s1[top1])>=lev(s[i]))// If the priority level is still not as high as the symbol to enter , Continue to give s2 in 
               {
                   s2[++top2]=s1[top1--];
               }
               // At the end of the cycle , There is no symbol priority to enter s1 The stack top symbol of has high priority , You can deposit s1 in 
               s1[++top1]=s[i];
               continue;
           }
           if(lev(s1[top1])<lev(s[i])&&s[i]!=')')
           {
               s1[++top1]=s[i];
           }
           if(s[i]==')')// Yes  ' ) '
           {
               while(s1[top1]!='(')// take s1 The symbols in are given to s2 in , Until I met  ' ) '
               {
                   s2[++top2]=s1[top1--];
               }
               top1--;
               continue;
           }
       }
   }
   while(top1>0)// if s1 And symbols , Need to give s2 in 
	{
		s2[++top2]=s1[top1--];
	}
	for(int i=1;i<=top2;i++)
    {
        cout<<s2[i]<<" ";
    }
    cout<<endl;
    // Perfect infix to suffix 
    // Next, calculate 
    for(int i=1;i<=top2;i++)
    {
        p=i;
        if(s2[i]>='0'&&s2[i]<='9')
        {
            js[++topis]=s2[i]-'0';
        }
        else // For the sign , Operate on the two elements at the top of the stack , And store the results on the top of the stack 
        {
            // Pay attention to the first digit of the advanced stack 
            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();// Print every step 
        }
    }
	return 0;
}

The operation results are as follows ：