What is a stack?

Stack has several meanings, such as a linear table that follows the first-in-last-out rule (as opposed to "queue"); where the system allocates variable address space when the program is running, it follows the first-in-last-out principle (as opposed to "heap");In a storage medium of CPU registers, follow the principle of first-in, last-out when accessing

The stack we are talking about today is the first meaning

What is FIFO

First in, last out, that is, first in and last out.It's that simple.

For example I have data x, y, z.I put x on the stack first, then y on the stack, then z on the stack.When I want to take it out, first take out z, then take out y, then take out x

This is a simple diagram

Push to stack

Into the stack refers to data storage

pop

Popping refers to data fetching

The stack that C++ gives us

// import header file#include // stack is in std namespaceusing namespace std;// Define a stack, each element in the stack is of type intstack st;// push 1 to stackst.push(1);// push 2 onto the stackst.push(2);// return to top of stackint tmp = st.top();// pop, no return valuest.pop();// if stack is emptyif(st.empty());

What are parentheses :-)

Brackets are divided into parentheses "()", square brackets "[]", and curly brackets "{}", each of which is divided into left brackets "([{" and right brackets "}])".Each left parenthesis must be followed by the same right parenthesis, and the parentheses cannot be misplaced.i.e. ([{}]) but not ([{]})

What is a match for parentheses

To judge whether parentheses match is to judge whether the use of parentheses is reasonable.For details, see "What are parentheses" :-)

How to use the stack to judge whether brackets match?

Thoughts

The idea of ​​using stack judgment is as follows:

1. Traverse the string

2. If parentheses are found

1) Determine whether it is a left bracket

If it is a left parenthesis, push it to the stack

Otherwise (it is the right parenthesis), pop the stack, and compare the result with the parentheses traversed. If it is not a parenthesis of the same type, return -1 directly (indicating an error)

3. After the traversal is completed, no errors are found, and the correct 0 is returned (indicates correct)

Code implementation

For (yin), (wei), then (wo), then (bi), (jiao), see (lan), this code is written in a source file.In actual development, the type definition, function declaration, header file inclusion, etc. should be placed in a .h file, the function function should be placed in a .c file, and the main function should be placed in the main.c file.Don't follow me, just put it in one file

#include #include #include // define an enumeration of bracket typestypedef enum{LITTLE, // parenthesesMIDDLE, // square bracketsLARGE, // curly bracketsERROR // error}brackets_t;// get parenthesis typebrackets_t get_brackets_type(char c){brackets_t result;switch(c){case '(':case ')':result = LITTLE;break;case '[':case ']':result = MIDDLE;break;case '{':case '}':result = LARGE;break;default:result = ERROR;break;}return result;}// Determine if the parenthesis is a left parenthesis, return 1int is_left(char c){if(c == '(' || c == '[' || c == '{')return 1;return 0;}// pop the stack if the stack is empty, return -1, otherwise return the top element of the stack// This sentence defines a generic (type placeholder), which will be changed to a specific type during compilation// This placeholder is TtemplateT pop(std::stack *st){// Check if the stack is emptyif(!(*st).empty()){ // Normal call if not emptyT result = (*st).top();(*st).pop();return result;}// If empty, return -1 of type T// use a more powerful coercionT *tmp; // create a temporary (T *) variableint itmp = -1; // create a temporary int variabletmp = (T *)&itmp; // For tmp to store the address of itmp, a forced conversion is requiredreturn *tmp; // use T's access rule to read the address of itmp}// Judging whether the bracket combination is correct, return 0 correctlyint is_brackets_right(const char *str){std::stack st; // build stack// iterate over the stringint len ​​= strlen(str);for(int i = 0; i < len; i++){// store the type of the current parenthesisbrackets_t br = get_brackets_type(str[i]);// If it is a parenthesis, make a parenthesis judgmentif(br != ERROR){// if the current parenthesis is an opening parenthesisif(is_left(str[i]))// Then get the bracket type and store it on the stackst.push(br);// else pop the stack and compare the type with the current parenthesiselse {// pop the stackbrackets_t sr = pop(&st);// if the types are not equal return -1if(sr != br)return -1;}}}// end of the loop, if there is no problem, return 0return 0;}int main(void){char str[16];scanf("%s", str);int if_it = is_brackets_right(str);if(if_it == 0)printf("It is right\n");else printf("It is not right\n");return 0;}

This is the primary usage of the stack - judging whether the parentheses match