栈的应用之括号匹配算法

约定不等于承诺〃 2023-09-30 21:21 13阅读 0赞

### 算法思路： ###

>  *  初始化一个栈，命名为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;
    }

#### 效果图： ####

![4244d0b93ae34fd19fc77866f38155b7.png][]

[4244d0b93ae34fd19fc77866f38155b7.png]: https://img-blog.csdnimg.cn/4244d0b93ae34fd19fc77866f38155b7.png