Application 2- data structure of stack (C language)

Expression evaluation

1. How to evaluate an expression with a stack , The so-called expression evaluation is to give an expression and then find its value .
   To help the assistant unpack , Let's make the topic a little simpler , There are only operators and numbers in the expression , Operators are only multiplication and addition , The numbers are all single digits .
   Then give the code ,precode Judge two operations in a function a and b Of priority , If a If the priority is high, it returns 1;operate The function is based on the operator theta Calculation a and b Value , And return the calculation results ; calc The function is based on the evaluator at the top of the operator stack , The result of calculating the two numbers at the top of the number stack , And add the result to the number stack ,calc Let's put it to the end .
   Next, let's implement expression evaluation step by step , First define a in the main function int Type of Variable n, Indicates the length of the input expression , Then program input n.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define ERROR 0
#define OK 1

typedef struct Stack {
    
    int *elements;
    int max_size, top_index;
} Stack;

void init(Stack *s, int length) {
    
    s->elements = (int *)malloc(sizeof(int) * length);
    s->max_size = length;
    s->top_index = -1;
}

int push(Stack *s, int element) {
    
    if (s->top_index >= s->max_size - 1) {
    
        return ERROR;
    }
    s->top_index++;
    s->elements[s->top_index] = element;
    return OK;
}

int pop(Stack *s) {
    
    if (s->top_index < 0) {
    
        return ERROR;
    }
    s->top_index--;
    return OK;
}

int top(Stack *s) {
    
    return s->elements[s->top_index];
}

int empty(Stack *s) {
    
    if (s->top_index < 0) {
    
        return 1;
    } else {
    
        return 0;
    }
}

int precede(char a, char b) {
    
    if (a == '*' && b == '+') {
    
        return 1;
    } else {
    
        return 0;
    }
}

int operate(char theta, int a, int b) {
    
    if (theta == '+') {
    
        return a + b;
    } else {
    
        return a * b;
    }
}
//  such , except calc  function , We've finished the evaluation of the expression ,
//  Last , Let's put  calc  Function write complete , Remember this function ？
//  From the digital stack numbers  Pop up two numbers in ,  Through the operator stack  operators  The top operator of the stack calculates the result , Then add the result to the stack with numbers numbers  in .
//  First we define a int  Variable of type a,  Make it equal to the top element of the number stack , Then delete the stack top element .
//  Let's define a  int  Variable of type  b,  Make it equal to the number stack  numbers  Top element of , Then delete the stack top element .
//  Next , We use the arithmetic stack operators  The top of the stack operator calculates a  and  b  Result , This can call operate  Function to calculate , Let's add the results to the stack  numbers  in .
//  For the convenience of writing , Let's implement it in one line of code , Finally, don't forget to put the stack  operatos  Top element of   Delete .
  
void calc(Stack *numbers, Stack *operators) {
    
    int a = top(numbers);
    pop(numbers);
    int b = top(numbers);
    pop(numbers);
    push(numbers, operate(top(operators),a, b ));
    pop(operators);
}

void clear(Stack *s) {
    
    free(s->elements);
    free(s);
}

int main() {
    
    int n;
    scanf("%d",&n);
    //  Next, we define two stacks  numbers  and  operators,  Each is assigned a Stack  Type size space , Stack numbers  Used to store the number to be calculated , Then we call the initialization function.  init  Initialize it ;  Stack operators  Used to store the operator to be evaluated ,  Once defined, initialize it as well . The first parameter is the stack name , The second parameter is n,  Indicates the total number of stacks .
    //  Next   We define a string pointer  buffer ,  And assign  n + 1  Character size space ,  The expression used to record the input ,  Then let the program enter an expression .
    //  Next   We use it   Variable i  To cycle through   Input expression .
   //  First , Let's define a  int  Variable of type i,  The initial value is  0, And then write a while  loop , 
   //  Conditions  i  Less than n,  Remember to write curly braces .
   //  Next   We call  isdigit  Look at the function  buffer  Of   The first i  individual   Is a character a number , If it's a number   We add it to the digital stack .
   //  Let's write down the conditions first ,  For convenience ,  We put  else  sentence   Write it, too , We'll implement two conditions later , Remember to  if  and  else  The curly braces at the back are complete .
   //  If the first  i  individual   Characters are numbers , Then we call the insert function  push  hold   The number is added to the number stack  number  in .
   //  Hint , hold char  Type of characters   Turn into  int  Type of number , Let the character subtract ‘0’  that will do .  And then add  i  add 1 , Take this and look at the next one   character .
   //  If at present , Characters are not numbers , Then it must be an operator , Let's analyze it carefully , If the operator stack  operatos  It's empty , Or the priority of the current character is higher than operators  The rune at the top of the stack has high priority , Then you should add this operator to operators  in .
  //  Remember the judgment priority function given before precede,  Function has two arguments , Represent two operations respectively  a  and  b,  If  a  If the priority of is high, it returns 1, Otherwise return to 0, Here we can   Use functions precede  To determine the priority .
  //  If   Arithmetic stack  operators  It's empty , Or the priority of the current operator is higher than that of the operator at the top of the stack , Then we should add the operator to the operator stack  operators  in , And then let  i  Add  1
   
    Stack *numbers =  (Stack *)malloc(sizeof(Stack));
    init(numbers, n);
    Stack *operators =  (Stack *)malloc(sizeof(Stack));
    init(operators,n);
    char  *buffer = (char *)malloc(sizeof(char) * (n+1));
    scanf("%s", buffer);
    int i = 0;
    while (i < n) {
    
        if(isdigit(buffer[i])) {
    
            push(numbers, buffer[i] - '0');
            i++;
        } else {
    
            if(empty(operators) || precede(buffer[i], top(operators))) {
    
                push(operators, buffer[i]);
                i++;
            } else {
    
		// 9,  If the operator stack  operators  Not empty , And stack operators have better priority , So what we need to do is ,
		//  We should start from the digital stack  numbers  in   Pop up two elements , Use the operator at the top of the operator stack to calculate the result , Then add the results to numbers  in . This operation is the previous calc  function , So we can   Use functions to complete operations . Be careful calc  The parameters are in turn   yes  number  and  operators.  Next, we correspond to if  Conditional statements , hold else  Write the sentence well , And in else  In the sentence   call  calc  function .
		
                calc(numbers, operators);
            
            }
        }
    }
    //  So we just put while  The cycle is finished , Next, let's think about a problem ,while  At the end of the cycle , Has the final result been calculated ？
    //  The answer, of course, is not necessarily ,  Operator stack operators  May not be empty , If it is not empty, it indicates that there are still unprocessed operations , Here we also use a while  loop , If the operator stack  operators  Not empty , Then use its stack top operator to operate , until operators  Until it's empty .
    //  If the operator stack  operators  Not empty , Then from numbers  Two numbers pop up in the stack , Then use the operator at the top of the operator stack   Calculate , Then add the results to numbers  In the stack , Here we just call  calc  Function to operate .
   
    while (!empty(operators)) {
    
        calc(numbers, operators);
    }
     //  In this way, we have calculated all the operators , What about the final calculation result  ？
     //  Think about it , We found that the final result is the stack numbers  Of   Top element of stack .  We will have a while  Output the calculation result after the loop , Then output a new line .
     
    printf("%d\n",top(numbers));
    //  Before the end of the program ,  We should also free up the occupied memory .
    //  Here we need to release the digital stack  numbers  and   Operator stack  operators  Memory space occupied , We can do it by calling clear  Function to implement . in addition , We also need to release the string pointer  buffer  Memory space pointed to .
    
    clear(numbers);
    clear(operators);
    free(buffer);
    return 0;
}