Arithmetic expression evaluation
A typical problem solved by stack is the evaluation of arithmetic expressions, such as "3 + 4 * 2 - (1 + 1) #". In the process of expression calculation, it is not calculated immediately after reading an operation, but compared with the following operators to determine which one to calculate first.
In order to solve the problem, we must first make some agreements. An expression consists of operands, operators, and delimiters. Operators and operators are the main components of an expression, and delimiters mark the end of an expression. Expressions are divided into three categories: arithmetic expressions, relational expressions and logical expressions. Only arithmetic expressions are discussed here, and the expressions are simplified as follows:
(1) Assume that all arithmetic is integers.
(2) All operators are binary operations of integers and are represented by one character.
Secondly, the four rules of addition, subtraction, multiplication and division are determined: multiplication and division before addition and subtraction; Calculate from left to right, first within the brackets, and then outside the brackets. Based on this, the priority relationship between adjacent front and rear operators is shown in the table, where x1 represents the previous operator and x2 represents the current operator. For example, when x1 is -, x2 is +, the corresponding priority relationship is ">", which means that the priority of x1 is higher and needs to be calculated first. If the priority table is' 0 ', this item will not appear.

According to the above agreement, the corresponding calculation method is designed by using operands (OPND stack) and operators (OPTR stack):
(1) Initialization: set the OPND stack to empty, and the bottom element of the OPTR stack is the expression starter '#';
(2) Execution process:

Read each character in the expression in turn:
       If it is an operand, it is converted to the corresponding numerical value OPND Stack;
       Otherwise, operators, and OPTR Stack top operator of stack for priority comparison;
              If the priority of the stack top operator is lower than that of the current operator, the current operator presses the stack;
              If the stack top operator takes precedence over the current operator, then OPTR Stack pop-up operator OPND Two operands pop up from the stack, perform corresponding calculations, and count         
              Calculation result press in OPND Stack;
              If the priority of the stack top operator is equal to the current operator, the current operator is the right parenthesis, and the corresponding left parenthesis is from OPTR Pop up the stack.
After execution, the OPND The top element of the stack is returned as the operation result.

In the program, I realize the basic operation of the stack, the conversion of operand symbols to decimal numbers, and the definition of priority table, so the program is long:

The method described above is solved directly by infix expression. In addition, suffix expression can also be used to solve arithmetic expression.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<locale>

//The following is the basic operation of chain stack written by myself, and then the expression evaluation algorithm

#define OK 1
#define ERROR 0

typedef int Status;
typedef char ElemType1;

typedef struct LNode    //Stack element node
{
	ElemType1 data;    //data
	struct LNode* next;    //Point to next node
}LNode, * LinkStack;

Status InitStack(LinkStack& S)    //Chained stack initialization
{
	S = (LNode*)malloc(sizeof(LNode));
	if (S == NULL) exit(0);
	S->next = NULL;
	return OK;
}

Status DestroyStack(LinkStack& S)    //Chain stack destruction
{
	LNode* p = S;
	LNode* q = p;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	free(q);
	return OK;
}

Status ClearStack(LinkStack& S)    //Chain stack emptying
{
	if (S->next == NULL) return OK;
	LNode* p = S->next;
	LNode* q;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	S->next = NULL;
	return OK;
}

Status StackEmpty(LinkStack S)    //Chain stack empty judgment
{
	if (S->next == NULL) return OK;
	return ERROR;
}

Status StackLength(LinkStack S)    //Number of chain stack elements
{
	LNode* p = S;
	int i = 0;
	while (p->next)
	{
		i++;
		p = p->next;
	}
	return i;
}

Status GetTop(LinkStack S, ElemType1& e)    //Get the top element of the chain stack
{
	if (S->next == NULL) return ERROR;
	e = S->next->data;
	return OK;
}

Status StackTraverse(LinkStack S)    //Chained stack traversal
{
	if (S->next == NULL) return ERROR;
	LNode* p = S->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}

Status Push(LinkStack& S, ElemType1 e)    //Chain stack
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	if (p == NULL) exit(0);
	p->data = e;
	p->next = S->next;
	S->next = p;
	return OK;
}

Status Pop(LinkStack& S, ElemType1& e)    //Chain stack
{
	if (S->next == NULL) return ERROR;
	e = S->next->data;
	LNode* p = S->next;
	S->next = p->next;
	free(p);
	return OK;
}

typedef int ElemType2;

typedef struct LNode2    //Stack element node
{
	ElemType2 data;    //data
	struct LNode2* next;    //Point to next node
}LNode2, * LinkStack2;

Status InitStack2(LinkStack2& S)    //Chained stack initialization
{
	S = (LNode2*)malloc(sizeof(LNode2));
	if (S == NULL) exit(0);
	S->next = NULL;
	return OK;
}

Status DestroyStack2(LinkStack2& S)    //Chain stack destruction
{
	LNode2* p = S;
	LNode2* q = p;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	free(q);
	return OK;
}

Status ClearStack2(LinkStack2& S)    //Chain stack emptying
{
	if (S->next == NULL) return OK;
	LNode2* p = S->next;
	LNode2* q;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	S->next = NULL;
	return OK;
}

Status StackEmpty2(LinkStack2 S)    //Chain stack empty judgment
{
	if (S->next == NULL) return OK;
	return ERROR;
}

Status StackLength2(LinkStack2 S)    //Number of chain stack elements
{
	LNode2* p = S;
	int i = 0;
	while (p->next)
	{
		i++;
		p = p->next;
	}
	return i;
}

Status GetTop2(LinkStack2 S, ElemType2& e)    //Get the top element of the chain stack
{
	if (S->next == NULL) return ERROR;
	e = S->next->data;
	return OK;
}

Status StackTraverse2(LinkStack2 S)    //Chained stack traversal
{
	if (S->next == NULL) return ERROR;
	LNode2* p = S->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}

Status Push2(LinkStack2& S, ElemType2 e)    //Chain stack
{
	LNode2* p = (LNode2*)malloc(sizeof(LNode2));
	if (p == NULL) exit(0);
	p->data = e;
	p->next = S->next;
	S->next = p;
	return OK;
}

Status Pop2(LinkStack2& S, ElemType2& e)    //Chain stack
{
	if (S->next == NULL) return ERROR;
	e = S->next->data;
	LNode2* p = S->next;
	S->next = p->next;
	free(p);
	return OK;
}

char ComparePriority(ElemType1 e1, ElemType1 e2)    //Comparison of the current operator with the previous operator
{
	int i, j;
	//Design priority table
	switch (e1)    //Different operators correspond to different subscripts
	{
	case '+':
		i = 0;
		break;
	case '-':
		i = 1;
		break;
	case '*':
		i = 2;
		break;
	case '/':
		i = 3;
		break;
	case '(':
		i = 4;
		break;
	case ')':
		i = 5;
		break;
	case '#':
		i = 6;
		break;
	default:
		break;
	}
	switch (e2)
	{
	case '+':
		j = 0;
		break;
	case '-':
		j = 1;
		break;
	case '*':
		j = 2;
		break;
	case '/':
		j = 3;
		break;
	case '(':
		j = 4;
		break;
	case ')':
		j = 5;
		break;
	case '#':
		j = 6;
		break;
	default:
		break;
	}
	char prior[7][7];    //A two-dimensional array is used to store the priority comparison results between the current element and the top element of the stack
	prior[0][0] = '>'; prior[0][1] = '>'; prior[0][2] = '<'; prior[0][3] = '<'; prior[0][4] = '<'; prior[0][5] = '>'; prior[0][6] = '>';
	prior[1][0] = '>'; prior[1][1] = '>'; prior[1][2] = '<'; prior[1][3] = '<'; prior[1][4] = '<'; prior[1][5] = '>'; prior[1][6] = '>';
	prior[2][0] = '>'; prior[2][1] = '>'; prior[2][2] = '>'; prior[2][3] = '>'; prior[2][4] = '<'; prior[2][5] = '>'; prior[2][6] = '>';
	prior[3][0] = '>'; prior[3][1] = '>'; prior[3][2] = '>'; prior[3][3] = '>'; prior[3][4] = '<'; prior[3][5] = '>'; prior[3][6] = '>';
	prior[4][0] = '<'; prior[4][1] = '<'; prior[4][2] = '<'; prior[4][3] = '<'; prior[4][4] = '<'; prior[4][5] = '='; prior[4][6] = '0';
	prior[5][0] = '>'; prior[5][1] = '>'; prior[5][2] = '>'; prior[5][3] = '>'; prior[5][4] = '0'; prior[5][5] = '>'; prior[5][6] = '>';
	prior[6][0] = '<'; prior[6][1] = '<'; prior[6][2] = '<'; prior[6][3] = '<'; prior[6][4] = '<'; prior[6][5] = '0'; prior[6][6] = '=';

	return prior[i][j];    //Returns the priority comparison result between the top element of the stack and the current element
}

//A function that converts a character number to a decimal number
int Atoi(char* str, int len)
{
	assert(str != NULL);
	int i = 0;
	int flag = 1;//Sign bit
	int tmp = 0;
	for (; i < len; i++)
	{
		if (str[i] == '-')
		{
			flag = -1;
		}
		if (isdigit(str[i]))
		{
			str[i] -= '0';
			tmp = tmp * 10 + str[i];
		}
	}
	return tmp * flag;
}

Status Operate(int a, char theta, int b)    //Operate on two numbers according to the operator theta
{
	int m;    //Save calculation results
	switch (theta)
	{
	case '+':
		m = a + b;
		break;
	case '-':
		m = a - b;
		break;
	case '*':
		m = a * b;
		break;
	case '/':
		m = a / b;
		break;
	default:
		break;
	}
	return m;
}

Status CalculateExpression(char* str)    //Expression evaluation algorithm
{
	//Evaluation of arithmetic expression using OPND and OPTR stack
	LinkStack OPTR;
	LinkStack2 OPND;
	InitStack2(OPND);
	InitStack(OPTR);
	Push(OPTR, '#');    //Press the expression terminator '#' into the OPTR stack
	//Read in each character of the expression in turn
	int i = 0;
	int j = 0;
	char str1[20];
	ElemType1 theta1;
	ElemType1 theta;
	GetTop(OPTR, theta1);
	int data;
	int flag = 0;
	int a, b;
	char s;
	while (str[i] != '#' || theta1 != '#')
	{
		//If it is an operand, press it into the OPND stack
		if (str[i] >= '0' && str[i] <= '9')
		{
			str1[j] = str[i];
			j++;
			i++;    //i move to the next position
			if (str[i] < '0' || str[i] > '9')
			{
				flag = 1;
			}
			if (flag == 1 && j > 0)
			{
				data = Atoi(str1, j);
				Push2(OPND, data);
				flag = 0;
				j = 0;
			}
		}
		else
		{
			GetTop(OPTR, theta1);    //View the OPTR operator theta1
			//The stack top element theta1 is compared with the current element according to the priority table
			s = ComparePriority(theta1, str[i]);
			switch (s)
			{
			case '<':    //If the operation priority at the top of the stack is low, the current operation is pressed on the stack
				Push(OPTR, str[i]);
				i++;
				break;
			case '>':    //If the operation priority at the top of the stack is high, the calculation is performed, and the calculation result is pushed into the OPND stack
				Pop(OPTR, theta);
				Pop2(OPND, b);
				Pop2(OPND, a);
				Push2(OPND, Operate(a, theta, b));
				break;
			case '=':
				Pop(OPTR, theta);
				i++;
				break;
			default:
				break;
			}
		}
		GetTop(OPTR, theta1);
	}
	int result;
	GetTop2(OPND, result);
	return result;
}

int main()
{
	char str[20];
	printf("Enter arithmetic expression(with'#’(end): ");
	gets(str);
	int result;
	result = CalculateExpression(str);
	printf("The result is:%d\n", result);
	return 0;
}

The operation results are as follows: