# Application 2- data structure of stack (C language)

2022-05-15 05:21:49

## 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;
}
``````