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
Daily Recommendation
views 10
views 4
views 4
views 3
views 3