Infix expression is converted to suffix expression (C language code + detailed explanation)

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Infix expression to suffix expression （ Ideas ）

1. Create a stack 2. Get infix expressions from left to right

a. Digital direct output b. Operator Situation 1 ： Left parenthesis encountered Direct stack , encounter Right bracket In the stack Left parenthesis After that, all operators on the stack pop up and output , meanwhile The left bracket comes out of the stack but does not output .

Situation two ： Encounter multiplication sign and division sign Direct stack , Until you encounter an operator with a lower priority , Play the stack in turn .

Situation three ： Plus and minus signs encountered , If at this time The stack is empty , be Direct stack , otherwise , In the stack High priority The operators of pop-up stack in turn （ Be careful ： The plus and minus signs belong to the same priority , So play the stack in turn ） until Stack empty or encounter left parenthesis until , Stop playing stack .（ Because the left bracket will pop up only when it matches the right bracket ）.

Situation four ： After obtaining , Pop up the remaining operation symbols in the stack and output

example : For example, will :2*(9+6/3-5)+4 Convert to suffix expression 2 9 6 3 / +5 – * 4 +

The conversion algorithm code is as follows ：

/* Infix to suffix function */
void Change(SqStack *S,Elemtype str[])
{
	int i=0;
	Elemtype e;
	InitStack(S);
	while(str[i]!='\0')
	{
		while(isdigit(str[i])) 
		{/* Filter numeric characters , Direct output , Until the next non numeric character print space jumps out of the loop  */
			printf("%c",str[i++]);
			if(!isdigit(str[i]))
			{
				printf(" ");
			}
		}
		/* Addition and subtraction operators have the lowest priority , If the element at the top of the stack is empty, it will be directly put on the stack , Otherwise, it will be stored in the stack 
		 All operators of play stack , If you encounter an open parenthesis, stop , Press the pop-up left bracket from the new stack , Because left 
		 The parentheses pop up when they want to match the parentheses again , This will be discussed separately later . After popping up, press the operator with low priority into the stack */
		if(str[i]=='+'||str[i]=='-')
		{
			if(!StackLength(S))
			{
				PushStack(S,str[i]);
			}
			else
			{
				do
				{
					PopStack(S,&e);
					if(e=='(')
					{
						PushStack(S,e);
					}
					else
					{
						printf("%c ",e);
					}
				}while( StackLength(S) && e != '(' );
				
				PushStack(S,str[i]);
			}
		}
		/* When you encounter the right parenthesis , Pop up the remaining operators in brackets , Until the left bracket is matched 
		 The left bracket only pops up and does not print （ The right bracket does not press the stack ）*/
		else if(str[i]==')')
		{
			PopStack(S,&e);
			while(e!='(')
			{
				printf("%c ",e);
				PopStack(S,&e);
			}
		}
		/* ride 、 except 、 The left parentheses are high priority , Press the stack directly */
		else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
		{
			PushStack(S,str[i]);
		}
		
		else if(str[i]=='\0')
		{
			break;
		}
		
		else
		{
			printf("\n Input format error ！\n");
			return ;
		}
		i++;
	}
	/* Finally, flip the remaining operators in the stack in turn and print */
	while(StackLength(S))
	{
		PopStack(S,&e);
		printf("%c ",e);
	}
}

Copy

The complete code is as follows ：

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h> 
#include<assert.h>

#define INITSIZE  20
#define INCREMENT 10
#define MAXBUFFER 20
#define LEN  sizeof(Elemtype)

/* Dynamic allocation storage structure of stack */ 
typedef char Elemtype;
typedef struct{
	Elemtype *base;
	Elemtype *top;
	int StackSize;
}SqStack;

/* Initialization stack */
void InitStack(SqStack *S)
{
	S->base=(Elemtype*)malloc(LEN*INITSIZE);
	assert(S->base !=NULL);
	S->top=S->base;
	S->StackSize=INITSIZE;
}

/* Stack pressing operation */ 
void PushStack(SqStack *S,Elemtype c)
{
	if(S->top - S->base >= S->StackSize)
	{
		S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT));
		assert(S->base !=NULL);
		S->top =S->base+S->StackSize;
		S->StackSize+=INCREMENT;
	}
	*S->top++ = c;
}
/* Ask for stack length */
int StackLength(SqStack *S)
{
	return (S->top - S->base);
}
/* Pop stack operation */
int PopStack(SqStack *S,Elemtype *c)
{
	if(!StackLength(S))
	{
		return 0;
	}
	*c=*--S->top;
	return 1;
}

/* Infix to suffix function */
void Change(SqStack *S,Elemtype str[])
{
	int i=0;
	Elemtype e;
	InitStack(S);
	while(str[i]!='\0')
	{
		while(isdigit(str[i])) 
		{/* Filter numeric characters , Direct output , Until the next non numeric character print space jumps out of the loop  */
			printf("%c",str[i++]);
			if(!isdigit(str[i]))
			{
				printf(" ");
			}
		}
		/* Addition and subtraction operators have the lowest priority , If the element at the top of the stack is empty, it will be directly put on the stack , Otherwise, it will be stored in the stack 
		 All operators of play stack , If you encounter an open parenthesis, stop , Press the pop-up left bracket from the new stack , Because left 
		 The parentheses pop up when they want to match the parentheses again , This will be discussed separately later . After popping up, press the operator with low priority into the stack */
		if(str[i]=='+'||str[i]=='-')
		{
			if(!StackLength(S))
			{
				PushStack(S,str[i]);
			}
			else
			{
				do
				{
					PopStack(S,&e);
					if(e=='(')
					{
						PushStack(S,e);
					}
					else
					{
						printf("%c ",e);
					}
				}while( StackLength(S) && e != '(' );
				
				PushStack(S,str[i]);
			}
		}
		/* When you encounter the right parenthesis , Pop up the remaining operators in brackets , Until the left bracket is matched 
		 The left bracket only pops up and does not print （ The right bracket does not press the stack ）*/
		else if(str[i]==')')
		{
			PopStack(S,&e);
			while(e!='(')
			{
				printf("%c ",e);
				PopStack(S,&e);
			}
		}
		/* ride 、 except 、 The left parentheses are high priority , Press the stack directly */
		else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
		{
			PushStack(S,str[i]);
		}
		
		else if(str[i]=='\0')
		{
			break;
		}
		
		else
		{
			printf("\n Input format error ！\n");
			return ;
		}
		i++;
	}
	/* Finally, flip the remaining operators in the stack in turn and print */
	while(StackLength(S))
	{
		PopStack(S,&e);
		printf("%c ",e);
	}
}

int main()
{
	Elemtype str[MAXBUFFER];
	SqStack S;
	gets(str);
	Change(&S,str);
	return 0;
}

Copy

The operation effect screenshot is as follows ：

How to calculate the value after converting infix expression into suffix expression

(https://blog.csdn.net/qq_42552533/article/details/86562791)

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/148663.html Link to the original text ：https://javaforall.cn