There is a complete code at the end of the article. Readers who have questions can discuss it together in the comment area, or they can communicate and learn together through private messages.
1: Question requirements
<1>Case Analysis
Any expression is composed of operands, operators and delimiters, collectively called words. Generally, the operand can be a constant or an identifier defined as a variable or constant; operators can be divided into three categories: arithmetic operators, relational operators and logical operators; basic delimiters include left and right brackets and expressions Ending characters, etc. For the sake of brevity, only the evaluation of simple arithmetic expressions is discussed here. This expression only contains four operators: addition, subtraction, multiplication, and division. It is not difficult for the reader to generalize this to more general expressions.
Below, operators and delimiters are collectively called operators; we know that the four arithmetic operations follow the following three rules:
1>Multiplication and division first, then addition and subtraction
2>Count from left to right
3>First inside the brackets and then outside the brackets
According to the above three operation rules, in each step of the operation, the precedence relationship between any two consecutive operators theta1 and theta2 is at most one of the following three relationships:
theta1
theta1=theta2, that is, the priority of theta1 is equal to theta2
theta1>theta2, that is, theta1 has a higher priority than theta2
1: Priority relationship table between operators:
According to rule (1), multiplication and division operations are performed first, and then addition and subtraction operations are performed, so there are ” + ” < "*" , " + " <" /" , "*" > ” + ” , “/” > ” + ” wait.
According to rule (2), the operation follows left associativity. When two operators are the same, the operator that appears first has higher priority, so there are ” + ” > ” + “, “-” > “-“, “*” > “*”, “/” > “I”.
According to rule (3), the priority in the brackets is higher. When tahta1 is ” + ” “_” “*” and “/”, the priority is lower than when tahta2 is “(“, but higher than when tahta2 is “)” priority.
“(“=”)” in the table indicates that when the left and right brackets meet, the operation within the brackets has been completed. For ease of implementation, assume that each expression starts with “#” and ends with “#”. So “#” = “#” means that the entire expression has been evaluated. There is no priority relationship between “)” and “(“, “#” and “)”, and “(” and “#”. This is because they are not allowed to appear one after another in the expression. Once this happens, you can It is considered that a syntax error has occurred. In the following discussion, we temporarily assume that the entered expression does not have a syntax error.
【Case implementation】
You can use two work stacks to implement expression evaluation algorithms, one called OPTR to store operators; the other called OPND to store operands or operation results.
<2>[Algorithm steps]
①Initialize the OPTR stack and OPND stack, and push the expression starting character “#” into the OPTR stack.
② Read the expression and read the first character ch. If the expression has not been read to “#” or the top element of OPTR is not “#”, the following operations will be executed in a loop.
●If ch is not an operator, push the OPND stack and read the next character ch.
●If ch is an operator, different processing will be done based on the priority comparison result between the top element of OPTR and ch:
>If it is less than, push ch onto the OPTR stack and read the next character ch;
>If it is greater than, pop up the operator on the top of the OPTR stack, pop up two numbers from the OPND stack, perform the corresponding operation, and push the result into the OPND stack;
>If equal, then the top element of the OPTR stack is “(” and ch is “)”. At this time, the “(” on the top of the OPTR stack is popped up, which is equivalent to successful bracket matching, and then reading the next character ch.
OPND The top element of the stack is the expression evaluation result, and this element is returned.
Theoretical guidance “Data Structure C Language Second Edition” edited by Yan Weimin….
2: ASCII code reference table:
3: Enter the process idea table:
2. Code implementation
<1>.cpp file
#include"Module.h"
int main()
{
char ch,x;//operator used to store push onto stack
char theta;//Operator used to store pop-up stack
char a,b;//used to store operand values
LinkStack OPTR;//operator stack
LinkStack OPND; //operand stack
InitStack(OPTR);//Initialization stack
InitStack(OPND);
Push(OPTR, '#');//Push # into the operator stack OPTR
scanf_s("%c", & amp;ch);//Both numbers and characters are input and stored in the form of character char in this example
getchar();
while (ch != '#' || GetTop(OPTR) != '#')
{
if (!In(ch))//If it is not an operator:
{
Push(OPND, ch);//Push numeric characters into the OPND stack
scanf_s("%c", & amp;ch);//Continue reading the next element
getchar();//Solve the problem that the input function cannot input characters normally due to the buffer.
}
else
switch (Precede(GetTop(OPTR), ch))//Compare the top element of OPTR's stack with the priority of ch
{
case '<':
Push(OPTR, ch);//If the priority is greater than the operator on the top of the stack, push it into the OPTR stack
scanf_s("%c", & amp;ch);//Continue reading the next character
getchar();
break;
case '>':
Pop(OPTR, theta);//If it is less than the top operator of the stack, pop the top operator of the stack
Pop(OPND, b);//Pop two elements in the OPND stack at the same time for operation
Pop(OPND, a);//Example: 7-2, enter 2 first and then enter 7, pop b2 first and then pop a7
Push(OPND, Operate(a, theta, b));//Do operation 7-2, and then push the operation result into the number stack OPND
break;
case '=':
Pop(OPTR, x);
scanf_s("%c", & amp;ch);
getchar();
break;
}
}
printf("The expression calculation result is: %d\
",GetTop(OPND) - 48);//The data type returned by GetTop is char type, subtract 48 to get the int type we need
return true;
}
<2>.h file
#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define ElemType int
//The storage structure of the chain stack
typedef struct StackNode//Use typedef to give struct StackNode aliases SN and *LinkStack
{
ElemType data;//data field
StackNode* next;//Pointer field
}StackNode, * LinkStack;//Define two structure types where LinkStack is a pointer to the structure
//Initialization function
//The initialization operation of the chain stack is to construct an empty stack. Since there is no need to set the head node, just set the top pointer of the stack to empty.
int InitStack(LinkStack & S)
{
S = NULL;
return true;
}
//Push to stack
int Push(LinkStack & S,char Ele)
{
LinkStack p;//Define the type of p as a pointer to the structure SN
p = new StackNode;//Generate a new node and apply for space for p
p->data = Ele;//Assign the data field of the new node to data
p->next = S;//Insert the new node to the top of the stack
S = p;//Modify the top pointer of the stack to p
return true;
}
//pop
int Pop(LinkStack & S,char & Ele)//Pop the top element of the stack to the variable Ele
{
LinkStack p;
if (S == NULL)
{
return false;
}
else
{
Ele = S->data;//Assign the value of the top element of the stack to the variable
p = S;//Use p to temporarily save the space of the top element of the stack for release
S = S->next;//Modify the top pointer of the stack
delete p;//Release the space of the top element of the stack
return true;
}
}
//Get the top element of the stack
int GetTop(LinkStack & S)
{
if (S == NULL)
{
return false;
}
else
{
return S->data;//Return the top element of the stack
}
}
//Traverse the chain stack elements
int Traversal(LinkStack & S)
{
LinkStack p;
p = S;
if (p == NULL)
{
printf("The link stack is empty!!\
");
return false;
}
else
{
printf("The data stored in the chain stack is: ");
for (p = S; p != NULL; p = p->next)//Linked list loop
{
printf("%d\t", p->data);
}
printf("\
");
return true;
}
}
//In determine whether ch is an operator
int In(char ch)
{
char arr[7] = { ' + ','-','*','/','(',')','#' };
for (int i = 0; i < 7; i + + )
{
if(ch==arr[i])//Traverse the char array, if it is in the array, it is judged as an operator and returns true, otherwise it returns false
{
return true;
}
}
return false;
}
//Determine operator priority
char Precede(char theta1, char theta2)//Get the corresponding output according to the precedence relationship table between operators
{
if ((theta1 == '(' & amp; & amp; theta2 == ')') || (theta1 == '#' & amp; & amp; theta2 == '#'))
{
return '=';
}
else if (theta1 == '(' || theta1 == '#' || theta2 == '(' || (theta1 == ' + ' & amp; & amp; (theta2 == '*' || theta2 == '/')) || (theta1 == '-' & amp; & amp; (theta2 == '*' || theta2 == '/')))
{
return '<';
}
else
return '>';
}
//'#'35'*'42 ' + '43 in ASCII code
char Operate(char a, char theta, char b)
{
switch (theta)//The function return type is char
{
case ' + '://For numbers, the difference between the decimal numbers corresponding to the char type and the int type is 48. The decimal number corresponding to the ASCII code of '0' is 48
return (a - '0') + (b - '0') + 48;//After converting the char type character to the int type for operation, add 48 to convert it into a character type number
case '-': //Example 34-32=2 2 + 48=50 50 is the ASCII value corresponding to 2
return (a - '0') - (b - '0') + 48;
case '*':
return (a - '0') * (b - '0') + 48;
case '/':
return (a - '0') / (b - '0') + 48;
}
return 0;//The function returns 0 when the previous statement does not return successfully
}
<3>Run results
Note: When inputting, the results obtained by the Chinese “()” and the English ‘()’ will be different. The reason is that the decimal numbers corresponding to the two in the ASCII code are different. For correct input, you should use the English input method of ‘()’
