栈的应用之括号匹配算法

算法思路：

• 初始化一个栈，命名为s

• 依次遍历待匹配的字符串

  • 如果当前字符为左括号（即'(', '[', '{'中的任意一个），则将其入栈

  • 如果当前字符为右括号（即')', ']', '}'中的任意一个），则需要进行匹配检测

    • 若栈为空，则无法匹配，返回false

    • 否则，将栈顶元素与当前右括号进行匹配，如果匹配成功，则将栈顶元素出栈;如果匹配失败，则返回false

• 若字符串中所有字符都已遍历完毕，则需要检测栈是否为空

  • 如果栈为空，则说明括号匹配成功，返回true

  • 否则，说明还有左括号未匹配到右括号，返回false

代码：

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

#define MaxSize 100  // 栈的最大容量

// 定义栈结构体
typedef struct {
    char data[MaxSize];
    int top;  // 栈顶指针
} Stack;

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

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

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

// 元素入栈
void push(Stack *s, char c) {
    if (is_full(s)) {
        printf("栈已满！\n");
        exit(EXIT_FAILURE);
    }
    s->top++;
    s->data[s->top] = c;
}

// 元素出栈
char pop(Stack *s) {
    if (is_empty(s)) {
        printf("栈为空！\n");
        exit(EXIT_FAILURE);
    }
    char c = s->data[s->top];
    s->top--;
    return c;
}

// 判断括号序列是否匹配
bool is_matched(char *str) {
    Stack s;
    init(&s);  // 初始化栈
    int i = 0;
    while (str[i] != '\0') {  // 遍历字符串
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            push(&s, str[i]);  // 左括号入栈
        } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            if (is_empty(&s)) {  // 栈为空，无法匹配
                return false;
            } else if ((str[i] == ')' && pop(&s) != '(') ||
                       (str[i] == ']' && pop(&s) != '[') ||
                       (str[i] == '}' && pop(&s) != '{')) {  // 栈顶元素与右括号不匹配
                return false;
            }
        }
        i++;
    }
    return is_empty(&s);  // 栈为空，则括号匹配成功，否则匹配失败
}

// 测试代码
int main() {
    char str[MaxSize];
    printf("请输入括号序列：");
    scanf("%s", str);
    if (is_matched(str)) {
        printf("括号匹配成功！\n");
    } else {
        printf("括号匹配失败！\n");
    }
    return 0;
}

效果图：