Application of stack -- arithmetic expression calculation (infix to suffix, suffix calculation)

Application of stack -- arithmetic expression calculation (infix to suffix, suffix calculation)

Problem introduction: arithmetic expression calculation is a basic problem in compiling system, and its implementation method is a typical application of stack. Any arithmetic expression is made up of operands, operators, and separators. Operands and operators are the main parts of an arithmetic expression, and the delimiter marks the end of an arithmetic expression. We call operands, operators and separators the words of an arithmetic expression. For convenience, only add, subtract, multiply and divide operations are designed here.
The arithmetic expression is evaluated in two steps:

  • Infix expression to suffix expression
  • Evaluation of the suffix expression.

1, Infix expression to suffix expression

1. Basic operation rules:

  • Multiply and divide before add and subtract
  • Inside bracket first, then outside bracket
  • Same level first left then right

2. The algorithm is as follows:

  • Set a stack, initially set the stack top element to "X"

  • The infix arithmetic expression is read in sequence, and when it is read but the next time is an operand, it is output, and then the next word is read.

  • When the read word is an operator, let x1 be the variable of the current stack top operator, X2 be the variable of the current scan read operator, assign the current read word to variable X2, and then compare the priority of variable x1 with that of variable x2.

  • If the priority of x1 is higher than that of x2, then x1 is backstacked as an output of the suffix arithmetic expression, and then the priority of the new stack top operator x1 and x2 are compared.

  • If the priority of x1 is lower than that of x2, stack the value of x2, and then read the next word

  • If the priority of x1 is equal to the priority of x2 and x1 is "(", X2 is ")", stack x1 back and read the next word.

  • If the priority of x1 is equal to the priority of x2 and x1 is "×", X2 is "××", then the algorithm ends.
    3. Priority relation table.
    In the table, Θ 1 represents the top of stack operator and Θ 2 represents the currently scanned operator.

    4. Calculation process

2, Suffix expression evaluation

1. Algorithm idea:

  • Set a stack to store operands, scan suffix arithmetic expressions from left to right, and stack them before reading an operand, take two operands from the top of the stack before reading an operator, and change the operation represented by the operator, and stack the operation result as a new operand. This process continues until the suffix arithmetic expression is read, and finally stack The top operand is the result of changing the suffix expression.
    2. Calculation process

3, Code implementation

Header file: LinkStack.h

typedef char DataType;
typedef struct node
{
	DataType data;
	struct node *next;
}Stack;
//initialization
void StackInitiate(Stack **head)
{
	(*head)=(Stack *)malloc(sizeof(Stack));
	(*head)->next = NULL;
}
//Void judgment
int StackNotEmpty(Stack *head)
{
	if (head->next!=NULL)
		return 1;
	else
		return 0;
}
//Push 
int StackPush(Stack *head, DataType x)
{
	Stack *p;
	p = (Stack *)malloc(sizeof(Stack));
	p->data = x;
	p->next = head->next;
	head->next = p;
	return 1;
}
//Out of the stack
int StackPop(Stack *head, DataType *x)
{
	Stack *p;
	p = head->next;
	if(p == NULL)
	{
		printf("Stack is empty and cannot be released!");
		return 0;
	}
	else
	{
		head->next = p->next;
		*x=p->data;
		free(p);
		return 1;
	}
}
//Data element at the top of stack
int StackGet(Stack *head, DataType *x)
{
	Stack *p;
	p = head;
	if (p->next == NULL)
	{
		printf("Stack is empty and cannot be released!");
		return 0;
	}
	else
		*x = p->next->data;
	return 1;
}
//Cancel dynamic application space
void Destroy(Stack *head)
{
	Stack *p,*p1;
	p = head;
	while (p != NULL)
	{
		p1 = p;
		p = p->next;
		free(p1);
	}
}

Source file:

#include<stdio.h>
#include<stdlib.h>
#include"LinStack.h"
#define stkSize 20
#define maxSize 30
int isp(char op)            //Find the priority of the operator at the top of the stack
{
	switch (op)
	{
	case'#':return 0; break;
	case'(':return 1; break;
	case'*':return 5; break;
	case'/':return 5; break;
	case'+':return 3; break;
	case'-':return 3; break;
	case')':return 6; break;
	}
}
int icp(char op)       //Find the priority of the new read in operator
{
	switch (op)
	{
	case'#':return 0; break;
	case'(':return 6; break;
	case'*':return 4; break;
	case'/':return 4; break;
	case'+':return 2; break;
	case'-':return 2; break;
	case')':return 1; break;
	}
}
//Infix expression to suffix expression
void mid_to_last(char mid[],char last[])
{
	Stack *mystack;
	StackInitiate(&mystack);
	char ch,ch1,op;
	int i = 0,j = 0;
	StackPush(mystack,'#');
	ch = mid[i++];
	while (StackNotEmpty(mystack) && ch != '#')
	{
		if (ch >= '0'&&ch <= '9')
		{
			last[j++]=ch;
			ch = mid[i++];//Output operand, read next character
		}
		else
		{
			StackGet(mystack,&ch1);
			if (isp(ch1) < icp(ch))
			{
				StackPush(mystack, ch);//Go to the stack
				ch = mid[i++];         //Read next character
			}
			else if (isp(ch1)>icp(ch))
			{
				StackPop(mystack, &op);
				last[j++]=op;
			}
			else if(isp(ch1)==icp(ch))
			{
				StackPop(mystack, &op);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
					ch = mid[i++];
			}
		}
	}
	
}
//Suffix expression evaluation
int Calculate(char str[])
{
	
	DataType x,x1,x2;
	int i,x3,x4;
	Stack *head;
	StackInitiate(&head);
	for (i=0; str[i] != '\0'; i++)
	{
		if (str[i] >='0'&&str[i] <='9')//If a number is read, stack
		{
			StackPush(head,str[i]);
		}
		else                          //When the operator is read, two operands are backstacked to calculate the operator
		{                             //The data type of the Backstack is char type, which will be converted to int type during operation, and the result of operation will be converted to char type for stack in    
			StackPop(head, &x2);
			StackPop(head, &x1);
			x3 = int(x2 - 48);
			x4 = int(x1 - 48);
			switch (str[i])
			{
			case'+':
			{
				x4 = x4+x3;
				break;
			}
			case'-':
			{
				x4 = x4-x3;
				break;
			}
			case'*':
			{
				x4 = x4*x3;
				break;
			}
			case'/':
			{
				if (x3==0)
				{
					printf("Zero denominator error!");
				    exit(0);
				}
				else
				{
					x4 = x4/x3;
					break;
				}
			}
			}
		     	x1 = char(x4 + 48);                                             //The result of calculation is converted to character type
		    	StackPush(head,x1);                                            //Calculation result stack
		}
	}
	StackPop(head,&x);                                                      //Get the calculation results and store them in x
	x = int(x - 48);                                                        //Convert character type calculation result to int type
	return x;
}
int main()
{
	int x;
	char data[stkSize];
	printf("Please enter infix expression to convert:");
	scanf("%s",data);
	char last[maxSize]="";
	mid_to_last(data, last);       //Call infix to suffix function
	x=Calculate(last);             //Suffix expression evaluation
	printf("The suffix expression is:%s\n", last);
	printf("The suffix expression evaluates to:%d\n", x);
	return 0;
}

4, Operation results (just use the above 2 + (3-4 * 5) test)


It can be seen that the above analysis process and results are correct. In fact, students who are familiar with compilation principles can directly use "move in" and "Convention action" to realize the conversion from infix arithmetic expression to suffix arithmetic expression.

Posted on Thu, 04 Jun 2020 20:29:34 -0700 by pbdude23