括号匹配问题 栈c语言

括号匹配问题可以使用栈来解决。

算法思路：

1. 创建一个栈，用于存放左括号；

2. 从左到右遍历字符串中的每个字符，如果是左括号，则将其入栈；如果是右括号，则弹出栈顶元素，与当前字符进行匹配，匹配成功则继续遍历，匹配失败则返回false。

3. 若遍历完字符串后栈为空，则返回true，否则返回false。

以下是C语言实现代码：

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

#define STACK_MAX 100

typedef struct {
    char data[STACK_MAX];
    int top;
} Stack;

void stack_init(Stack *s) {
    s->top = 0;
}

bool stack_empty(Stack *s) {
    return s->top == 0;
}

bool stack_push(Stack *s, char c) {
    if (s->top == STACK_MAX) {
        return false;
    }
    s->data[s->top++] = c;
    return true;
}

char stack_pop(Stack *s) {
    if (stack_empty(s)) {
        return '\0';
    }
    return s->data[--s->top];
}

bool is_match(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

bool is_valid(char *s) {
    Stack stack;
    stack_init(&stack);
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            stack_push(&stack, s[i]);
        } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
            char left = stack_pop(&stack);
            if (!is_match(left, s[i])) {
                return false;
            }
        }
    }
    return stack_empty(&stack);
}

int main() {
    char s[] = "({[]})";
    if (is_valid(s)) {
        printf("Valid\n");
    } else {
        printf("Invalid\n");
    }
    return 0;
}