c 用栈实现括号匹配算法

括号匹配算法是指检查给定字符串中的括号是否匹配的算法。其中，栈是实现该算法的常用数据结构。在遍历字符串时，我们可以将左括号入栈，当遇到右括号时，再将栈顶元素弹出。如果弹出的左括号与当前右括号不匹配，或者栈已空而遇到右括号，则说明括号不匹配。

以下是使用 C 语言实现括号匹配算法的代码：

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

#define MAX_SIZE 100

// 定义栈结构体
typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack* s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈
void push(Stack* s, char c) {
    if (isFull(s)) {
        fprintf(stderr, "Stack is full!\n");
        exit(EXIT_FAILURE);
    }
    s->data[++s->top] = c;
}

// 出栈
char pop(Stack* s) {
    if (isEmpty(s)) {
        fprintf(stderr, "Stack is empty!\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

// 括号匹配算法
bool checkBrackets(char* str) {
    Stack s;
    initStack(&s);

    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            push(&s, str[i]);
        } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            if (isEmpty(&s)) {
                return false;
            }
            char c = pop(&s);
            if ((str[i] == ')' && c != '(') || (str[i] == ']' && c != '[') || (str[i] == '}' && c != '{')) {
                return false;
            }
        }
    }

    return isEmpty(&s);
}

// 测试括号匹配算法
int main() {
    char str[MAX_SIZE];
    printf("Enter a string with brackets: ");
    scanf("%s", str);

    if (checkBrackets(str)) {
        printf("Brackets are matched!\n");
    } else {
        printf("Brackets are not matched!\n");
    }

    return 0;
}

在上面的代码中，我们首先定义了一个栈结构体，包含一个字符数组和一个栈顶指针。然后，我们定义了几个用于操作栈的函数，包括初始化栈、入栈、出栈、判断栈是否为空或已满等。最后，我们实现了括号匹配算法，使用栈来判断字符串中的括号是否匹配。在 main 函数中，我们通过用户输入一个字符串来测试括号匹配算法的正确性。