Typical application of "stack" - expression evaluation (implemented in C language)

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Expression evaluation is a basic problem in programming language compilation . Its implementation is right “ Stack ” Typical application of . This paper uses the simplest and intuitive algorithm for expression evaluation “ Operator first ”.

We all know that the operation rule of arithmetic four operations is ：

First, , Add or subtract after .

From left to right

Let's start with the brackets , And then you can count out the brackets

Expressions make up

Any expression has operands 、 Operators and delimiters .

Operands can be constants , It can also be an identifier described as a variable or constant .

Operators can be divided into arithmetic operations , Relational operations and logical operators .

Delimiters include left and right parentheses and terminators .

This article only uses arithmetic operation for convenience of demonstration .

Operator priority

For successive operators θ1 and θ2 There are three relationships ： Greater than 、 Equal to and less than . From this we can list “+-*/” Between priorities . The following table ：

	+	–	*	/	(	)	#
+	>	>	<	<	<	>	>
–	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=
)	>	>	>	>		>	>
#	<	<	<	<	<		=

The priority of addition, subtraction, multiplication and division is lower than “（” But higher than “）”, From the operation from left to right , When θ1=θ2 , Make θ1>θ2

In order to simplify the algorithm , Dummy one on the left and right of the expression “#”, This pair of “#” Indicates that the evaluation of an expression is completed .

“（”=“）” When a pair of parentheses meet, it means that the operation within the parentheses has been completed .

“）” and “（”、“#” and “(”、“(” and “#” Cannot appear one after another. If it appears, the expression has a syntax error .

To implement the priority algorithm , You can use two work stacks , One is OPTR, Used to register operator , One is OPND, It is used to register the operation number and operation result .

The basic idea of the algorithm .

First, set the operand stack to empty , The expression starts with “#” Is an element at the bottom of the stack .

Read each character in the expression in turn , If operand, enter OPND Stack , If it's an operator, it's the same as OPTR The stack top operator of the stack compares the priority and performs corresponding operations , Until the entire expression is evaluated （OPTR The top element of the stack and the currently read characters are “#”）

Code implementation ：

First, get familiar with the relevant operations of the stack ：

#include "stdio.h"
#include "malloc.h"

#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW    -2

typedef int  Status;
#define STACK_INIT_SIZE  100
#define STACKINCREMENT   10

typedef struct{
    SElemType *base;
    SElemType *top;
    int      stacksize;
}SqStack;
// Construct an empty stack 
Status InitStack(SqStack *S){
    S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

    if(!S->base)
        exit(OVERFLOW);
    S->top=S->base;
    S->stacksize=STACK_INIT_SIZE;
    return OK;
}
// Judge whether it is an empty stack 
Status StackEmpty(SqStack S){
    if(S.top == S.base)
        return TRUE;
    else
        return FALSE;
}
// use e return S The top element of 
Status GetTop(SqStack S, SElemType *e){
    if(S.top == S.base)
        return ERROR;
    *e = *(S.top-1);
    return OK;
}
// Insert e For the new top element 
Status Push(SqStack *S, SElemType e){
    if((S->top - S->base) >= S->stacksize){
        S->base = (
                    SElemType*)realloc(S->base,
                   (S->stacksize+STACKINCREMENT)*sizeof(SElemType)
                   );
        if(!S->base)
            exit(OVERFLOW);
        S->top = S->base +S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top)=e;
    S->top++;
    return OK;
}
// Delete S The top element of , And use e Return its value 
Status Pop(SqStack *S, SElemType *e){
    if(S->top == S->base)
        return ERROR;
    S->top--;
    *e = *(S->top);
    return OK;
}
// From the bottom of the stack to the top of the stack S Each element of the Visit（）, In case of failure, the operation is invalid 
Status ListTraverse(SqStack S,Status (*visit)(SElemType)){
    SElemType *p;
    p=S.base;
    for(p=S.base;p<S.top;p++)
        (*visit)(*p);

    return OK;
}
// Output elements e
Status output(SElemType e){
    printf("%d ",e);

    return OK;
}

Copy

Code that implements expression evaluation ：

/* Evaluate an integer expression 
 * The expression must be in # end 
 * Multiple digits can appear in the expression ,
 * Spaces can appear in expressions 
 * Operators include +,-,*,/,(,)
 * The result of the operation can be multiple integers , And return as an integer 
 */
typedef int SElemType;      /* The type of element put on the stack */
#include <ctype.h>
#include "stack_s.c"
/* Judge whether a character entered is an operator 
 *c Indicates the character entered 
 *op The array stores operators that the system can recognize 
 */
Status in(char c,char op[]){
    char *p;
    p=op;
    while(*p != '\0'){
        if(c == *p)
            return TRUE;
        p++;
    }
    return FALSE;
}
/* Compare the priority of two operators 
 *a,b Store the operators to be compared in 
 *'>' Express a>b
 *'0' Indicates an impossible comparison 
 */
char Precede(char a, char b){
    int i,j;
    char pre[][7]={         
	/* The priority between operators is made into a table */
        {'>','>','<','<','<','>','>'},
        {'>','>','<','<','<','>','>'},
        {'>','>','>','>','<','>','>'},
        {'>','>','>','>','<','>','>'},
        {'<','<','<','<','<','=','0'},
        {'>','>','>','>','0','>','>'},
        {'<','<','<','<','<','0','='}};
    switch(a){
        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;
    }
    switch(b){
        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;
    }
    return pre[i][j];
}
/* Perform actual operations 
 *a,b Two operands to be operated are stored in the form of integers 
 *theta Store characters representing operators in 
 * The result is returned as an integer 
 */
int Operate(int a, char theta, int b){
    int i,j,result;
    i=a;
    j=b;

    switch(theta)   {
        case '+': result = i + j; break;
        case '-': result = i - j; break;
        case '*': result = i * j; break;
        case '/': result = i / j; break;
    }
    return result;
}
/* Get the next integer or operator from the input buffer , And pass n Bring back to the main function 
 * The return value is 1 Indicates that the operator is obtained 
 * The return value is 0 Indicates that the obtained integer operand 
 */
int getNext(int *n){
    char c;
    *n=0;
    while((c=getchar())==' ');  /* Skip one or more spaces */
    if(!isdigit(c)){            /* Judge by function if the character is not a number , Then it can only be an operator */
        *n=c;
        return 1;
    }
    do    {                         /* Can execute this statement , The description character is a number , Here we use a loop to get consecutive numbers */
        *n=*n*10+(c-'0');       /* Convert consecutive numeric characters into corresponding integers */
        c=getchar();
    }    while(isdigit(c));         /* If the next character is a number , Enter the next cycle */
    ungetc(c,stdin);            /* The newly read character is not a number , It may be an operator , In order not to affect the next reading , Put the character back into the input buffer */
    return 0;
}

int EvaluateExpression(){

    int n;
    int flag;
    int c;
    char x,theta;
    int a,b;

    char OP[]="+-*/()#";
    SqStack  OPTR;
    SqStack  OPND;

    InitStack(&OPTR);      
    Push(&OPTR,'#');
    InitStack(&OPND);
    flag=getNext(&c);

    GetTop(OPTR, &x);
    while(c!='#' || x != '#')
    {
        if(flag == 0)
	     {
                  Push(&OPND,c);
                  flag = getNext(&c);
             }        else
	{
            GetTop(OPTR, &x);
            switch(Precede(x, c))
	    {
                case '<':// The top elements of the stack have low priority                     
                    Push(&OPTR,c);
                    flag = getNext(&c);
                    break;
                case '=':// Remove parentheses and accept the next character  
                    Pop(&OPTR,&x);
                    flag = getNext(&c);
                    break;
                case '>'：//  Back off the stack and put the operation result on the stack                                        
                    Pop(&OPTR, &theta);
                    Pop(&OPND,&b);
                    Pop(&OPND,&a);
                    Push(&OPND, Operate(a, theta, b));
                    break;
            }
        }
        GetTop(OPTR, &x);
    }
    GetTop(OPND, &c);
    return c;
}

void main(){
    int c;
    printf("Please input one expression:");
    c=EvaluateExpression();
    printf("Result=%d\n",c);
    getch();
}

Copy

Welcome to my website ： http://www.zblog.us/programing/cc/expression-stack.html | Zhao Jie's blog

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/148439.html Link to the original text ：https://javaforall.cn