## current position：Home>Application 2- data structure of stack (C language)

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

2022-05-15 05:21:49【java_ prinln】

## Expression evaluation

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

copyright notice

author[java_ prinln],Please bring the original link to reprint, thank you.

https://en.cdmana.com/2022/135/202205142228140794.html

## The sidebar is recommended

- Online FAQ positioning FAQ what is the cause of the high load problem?
- What is the function of getstatic, a common tool for online FAQs?
- Android 11 new soft keyboard occlusion / animation solution
- Common tools for online FAQs include?
- How does SAP commerce cloud configure new applications for storefront
- In the CMS GC process, what is the reason why the business thread puts objects into the old generation (the characteristics of concurrent collection)?
- How good and accurate is the recommendation?
- Online FAQ positioning FAQs what are the causes of continuous GC problems?
- Does the data reflect the real viewing experience?
- What are the reasons for fullgc (throw oom if FGC recovery is invalid)?

## guess what you like

Algorithm improvement - basic algorithm (turtle speed multiplication)

[C + +] sword finger offer 10 - I. Fibonacci sequence

Online FAQ positioning FAQ nosuchmethodexception what is the cause of the problem?

IOS enables native im development

What is the common function of SM?

"Automated testing" a new generation of Web front-end automated testing framework - playwright, get started quickly!

Online FAQ positioning FAQ what is the cause of the high load problem?

What is the function of watch, a common tool for online FAQs?

Timeliness in recommender systems, Zhang Fuguo et al. ESWA 2017

Alibaba's open source Java diagnostic tool uses what methods to diagnose.

## Random recommended

- What is the function of dashboard, a common tool for online FAQs?
- What is the role of JAD, a common tool for online FAQs?
- Online FAQ positioning FAQ what are the causes of high CPU utilization?
- 07 - explore the underlying principles of IOS | several OC objects [instance object, class object, metaclass], ISA pointer of object, superclass, method call of object and the underlying essence of class
- Extreme fox gitlab settled in Alibaba cloud computing nest to jointly improve the development experience on the cloud
- How does artificial intelligence help natural science
- Elementui upload file
- Modern CSS solution: CSS mathematical functions
- Create a general efficiency improvement solution for front desk + middle desk based on vue3 (network disk link)
- Brush 100 front-end high-quality interview real questions in 2 weeks, and the source code is complete
- Vue has reduced its workload by half since using components
- I built a front-end mock tool
- About uboot -- Ping virtual machine Ubuntu operation
- Video transcoder editready for Mac
- [taro] taro gets the detailed attributes of the element (solved)
- Picture and text difference comparison tool: kaleidoscope for Mac
- Background of spatiotemporal artificial intelligence
- The top 10 of oceanbase database competition was born, and the integration of industry and education accelerated the training of database talents
- China brand Day ｜ Youxuan software: strengthen its own brand and fight for China's database industry
- New feature release of gaussdb (for redis): enhanced prefix scanning and multi rent isolation
- CICC purchases the original maintenance service of gbase database in 2022
- Java implementation sequence table
- Simple implementation of linked list in Java
- C + + parameterless constructor (difference between stack and heap)
- Vue NPM startup error - solution
- With the introduction of Alibaba cloud database into Shandong medical insurance information platform, the settlement response speed increased by nearly 10 times
- Yixinhuachen was selected into the atlas of relevant manufacturers in the primary market of China's big data industry
- 2021-06-05 Java Foundation (day four): two ways of locking
- Android bangs screen and water drop screen are the best overall adaptation scheme
- Don't take detours in Android learning
- Android realizes Gaode map track playback
- 2021 preparing for the 1000 Java interview questions that gold, silver and four must brush
- The database function queries the MySQL database at the correct time
- Linux changes the SSH connection mode, changes the public key to the user name and password, and logs in
- Websocket + springboot message active push
- Java common classes and methods
- Go connect to the database (simple query learning)
- HTTP - understand HTTP protocol (I)
- Spring boot quickly switches the configuration of development environment and production environment (application. YML)
- Java gets the date of the previous day