c语言栈的括号匹配算法程序（A C Language Algorithm for Matching Brackets Using Stacks）

Introduction:

A stack is a data structure in computer science that stores and retrieves items in a last-in, first-out (LIFO) order. One common application of a stack is to check the syntax of programming languages, such as checking whether parenthesis are correctly matched. In this article, we will explore the C language algorithm for matching brackets using stacks.

Stack Implementation:

A stack can be implemented using an array or a linked list. In this article, we will use an array. The following is the structure of the stack:

struct Stack {
    int data[MAXSIZE];  // MAXSIZE is the maximum size of the stack
    int top;            // the position of the top element in the stack
};

The stack has an array of integers and a variable called \"top\" that tracks the position of the top element in the stack. Initially, the top position is set to -1 to indicate an empty stack. The stack operations are push, pop, and top. Push adds an element to the top of the stack, pop removes the top element of the stack, and top returns the value of the top element of the stack without removing it.

Algorithm:

The algorithm for matching brackets using stacks is as follows:

1. Initialize an empty stack
2. Traverse the string from left to right
3. If the character is an opening bracket (such as '('), push it onto the stack
4. If the character is a closing bracket (such as ')'), pop the top element from the stack
5. If the popped element is not the corresponding opening bracket, the brackets are not matching
6. At the end of the traversal, if the stack is not empty, the brackets are not matching

The time complexity of the algorithm is O(n), where n is the length of the input string.

Code:

The C code for the matching brackets algorithm using stacks is as follows:

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
struct Stack {
    char data[MAXSIZE];
    int top;
};
void push(struct Stack* stack, char element) {
    if (stack->top == MAXSIZE - 1) {
        printf(\"Stack is full\
\");
        return;
    }
    stack->top++;
    stack->data[stack->top] = element;
}
char pop(struct Stack* stack) {
    if (stack->top == -1) {
        printf(\"Stack is empty\
\");
        return '\\0';
    }
    char element = stack->data[stack->top];
    stack->top--;
    return element;
}
char top(struct Stack* stack) {
    if (stack->top == -1) {
        printf(\"Stack is empty\
\");
        return '\\0';
    }
    return stack->data[stack->top];
}
int isMatching(char opening, char closing) {
    if (opening == '(' && closing == ')') return 1;
    else if (opening == '[' && closing == ']') return 1;
    else if (opening == '{' && closing == '}') return 1;
    else return 0;
}
int checkBrackets(char* string) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1;
    int i;
    for (i = 0; string[i] != '\\0'; i++) {
        if (string[i] == '(' || string[i] == '[' || string[i] == '{') {
            push(stack, string[i]);
        }
        else if (string[i] == ')' || string[i] == ']' || string[i] == '}') {
            char element = pop(stack);
            if (!isMatching(element, string[i])) {
                return 0;
            }
        }
    }
    if (stack->top == -1) return 1;
    else return 0;
}
int main() {
    char string[MAXSIZE];
    printf(\"Enter a string: \");
    gets(string);
    if (checkBrackets(string)) {
        printf(\"Brackets are matching\
\");
    }
    else {
        printf(\"Brackets are not matching\
\");
    }
    return 0;
}

The code uses the stack structure we defined earlier. The functions push, pop, and top are used to manipulate the stack. The function isMatching checks whether an opening and a closing bracket match. The function checkBrackets implements the algorithm described earlier to check whether the brackets in the input string match. The main function reads input from the user and calls the checkBrackets function.