Experiment 3 Arithmetic expression evaluation （ Must do , Design experiment ）
*
Experimental purpose
Master the basic operation of stack , In depth understanding of stack characteristics , Be able to flexibly use them in the context of practical problems , And deepen the understanding of this structure .
*
Experiment content
Design a program , Demonstrate the process of evaluating arithmetic expressions with operator priority method . Input the correct syntax from the terminal in the form of character sequence , Integer expression without variables . Using textbook tables 3.1 Operator precedence relation given , Realize the evaluation of arithmetic four arithmetic mixed operation expression , And imitate the examples of textbooks 3-1 Demonstrate operator stack in evaluation , Operand stack , Changes in input characters and main operations . Test data can choose examples 3-1 Arithmetic expression of 3*（7-2）, Or optional .
*
Data structure definition
（ Explain the data structure used in your algorithm , Definition of data type ）
Stack is a linear table that can only be inserted or deleted at one end . Insert allowed in table , The end of the delete operation is called the top of the stack . The current position of the top of the stack is dynamic , The current position of the top of the stack is indicated by a position indicator called the top of the stack pointer . When there are no elements in the stack , Empty stack , Stack insertion and deletion operations are usually called stack entry and stack exit . The main feature of stack is last in first out .
Typedef struct{ SElemType *base; SElemType *top; Int stacksize; }SqStack;
stacksize Indicates the current maximum usable capacity of the stack .Base Time stack bottom pointer ,top As a pointer to the top of the stack .
*
Algorithm idea and algorithm design
（ Explain the idea of the algorithm in words first , Then give the class C Language algorithm ）
To implement operator first algorithm , We use two work stacks ,, One is called OPTR, Used to deposit operators ; The other is called OPND, Used to register operands or operation results , Read each character in sequence , Enter if operand OPND Stack , And if it is an operator OPTR The stack top operator of the stack compares the priority before the operation , Until the entire expression is evaluated .
void GetExpressionValue(){ SqStack OPTR,OPND; SElemType result;// Return the final result
InitStack(&OPTR); InitStack(&OPND); Push(&OPTR,'#');// Place the terminator at the bottom of the operator
printf(" Please enter an arithmetic expression :\n"); char c = getchar();
while(c!='#'||GetTop(&OPTR)!='#'){// When *c=='#'&& Stack top character =='#' When
if(isdigit(c)){// If it is a number, turn it into a number Then enter the operand stack int data[10]; int i,num; i =
num =0;//num Is a middle number Used to convert the number in the string into an integer and then put it on the stack i Used to store the characters in the string data array
while(isdigit(c)){ data[i] = c-'0'; i++; c = getchar(); } for(int
j=0;j<i;j++){ num = num*10+data[j]; } Push(&OPND,num);
}else{// If it is a character, put it on the operator stack SElemType a,b,theta;//a b theta It is used to return the elements in the operand stack and operator stack
switch(Priority(GetTop(&OPTR),c)){// Compare the characters to be put on the stack with the top of the stack Priority relationship of operators case
'<':Push(&OPTR,c); c = getchar(); break; case
'>':Pop(&OPND,&b); Pop(&OPND,&a); Pop(&OPTR,&theta);
Push(&OPND,Reckon(a,theta,b)); break;// Stack results case
'=':Pop(&OPTR,&theta); c = getchar(); break;// Description parentheses meet Delete the brackets in the stack
default:break; } }} Pop(&OPND,&result); printf(" The result is ：%d",result); }
*
Experiment code
（ Namely C Language program ）
#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define
STACKINCREMENT 5 #define STACK_INIT_SIZE 10 typedef char SElemType; typedef int
Status; typedef struct{ SElemType *base;// Stack bottom pointer SElemType *top;// Stack top pointer int
stacksize;// Currently allocated storage space }SqStack; char prior[7][7]={
{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','!'},{'>','>','>','>','!','>','>'},
{'<','<','<','<','<','!','='}};// A two-dimensional array that defines the precedence relationship between operators // Construct a storage char Empty stack of type data
Status InitStack(SqStack *s){ s->base = (SElemType
*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!s->base) return ERROR;
s->top = s->base;// The number of elements in the stack is 0 s->stacksize = STACK_INIT_SIZE; return OK; }
// Push Status Push(SqStack *s,SElemType e){ if(s->top-s->base>=s->stacksize){
s->base = (SElemType
*)realloc(s->base,(STACKINCREMENT+s->stacksize)*sizeof(SElemType));
if(!s->base) exit(0); s->top = s->base+s->stacksize; s->stacksize +=
STACKINCREMENT; } *s->top++ = e; return OK; } // Out of stack Status Pop(SqStack
*s,SElemType *e){ if(s->base==s->top){ printf(" Empty stack !\n"); return ERROR; }
*e = *--s->top; return OK; } // Get the top element of the stack SElemType GetTop(SqStack *s){ return
*(s->top-1); } // Determine the subscript in the two-dimensional array if the input character is an operator If it is a number, it is separately distinguished from the operator It is convenient to enter the stack when entering the expression int
Index(char c){ switch(c){ case '+': return 0; case '-': return 1; case
'*': return 2; case '/': return 3; case '(': return 4; case ')': return
5; case '#': return 6; default: return 7; } } // Judge priority , Return size < > = ! char
Priority(char a,char b){ int x,y; x = Index(a); y = Index(b); if(x!=7&&y!=7)
return prior[x][y]; else return '!'; } // Simple expression evaluation int Reckon(int a,char
theta,int b){ switch(theta){ case '+':return a+b; case '-':return a-b;
case '*':return a*b; case '/':return a/b; } } // Judge whether a character is a number Status
isdigit(char ch){ if(ch>='0'&&ch<='9') return OK; return ERROR; } // Arithmetic expression evaluation
void GetExpressionValue(){ SqStack OPTR,OPND; SElemType result;// Return the final result
InitStack(&OPTR); InitStack(&OPND); Push(&OPTR,'#');// Place the terminator at the bottom of the operator
printf(" Please enter an arithmetic expression :\n"); char c = getchar();
while(c!='#'||GetTop(&OPTR)!='#'){// When *c=='#'&& Stack top character =='#' When
if(isdigit(c)){// If it is a number, turn it into a number Then enter the operand stack int data[10]; int i,num; i =
num =0;//num Is a middle number Used to convert the number in the string into an integer and then put it on the stack i Is used to store the characters in the string data array
while(isdigit(c)){ data[i] = c-'0'; i++; c = getchar(); }
for(int j=0;j<i;j++){ num = num*10+data[j]; } Push(&OPND,num);
}else{// If it is a character, put it on the operator stack SElemType a,b,theta;//a b theta It is used to return the elements in the operand stack and operator stack
switch(Priority(GetTop(&OPTR),c)){// Compare the characters to be put on the stack with the top of the stack Priority relationship of operators case
'<':Push(&OPTR,c); c = getchar(); break; case
'>':Pop(&OPND,&b); Pop(&OPND,&a); Pop(&OPTR,&theta);
Push(&OPND,Reckon(a,theta,b)); break;// Stack results case
'=':Pop(&OPTR,&theta); c = getchar(); break;// Description parentheses meet Delete the brackets in the stack
default:break; } } } Pop(&OPND,&result); printf(" The result is ：%d",result); }
* Algorithm test results
（ Explain test data , Paste the experimental result diagram ）
experimental data ：3*（5+2） 9/（5+2）
* Analysis and summary
（1） Algorithm complexity analysis and optimization , Defect analysis
（ Explain the complexity of your algorithm , What are the advantages and disadvantages of the algorithm ）
Data compression storage stack , Its operation mainly includes ：
Build stack int Push(SeqStack *S, char x) Push int Pop(SeqStack *S, char x) Out of stack .
The average time complexity of the above operations is O(n), The main time is spent in input operation .
（2） Experimental summary
（ Explain how you solve the problems encountered in the experiment , What are the gains ）
Through this experiment , Let me review the knowledge of stack , Enhanced my c Language programming ability .
It takes patience to do anything , It takes more patience to design and write programs . At the beginning , I write functions very fast , But when we finally debug, we find that the error is very hidden , It takes a lot of time . Later, I first conceived the functions and parameters of the function on paper , After considering the interface, you can start to compile it , It will be easier to succeed .
Technology