题解 | 括号配对问题

解题思路：

首先我们读到题目中的匹配规则为()[]或者[()]或者([])形式的括号类型，之后就是当我们找到左括号的时候一定要选取右括号进行匹配，于是我们需要进行开一个辅助栈，当遇见左括号的时候压入栈中，当遇见右括号的时候进行以下操作：

当辅助栈为空的时候我们认为直接不合法，原因就是离其最近的没有与之相匹配的括号因此不合法

当辅助栈不为空的时候需要括弧与括弧进行匹配，方括号与方括号进行匹配，如果匹配成功则辅助栈弹出栈顶元素，如果不匹配，则判断为不合法。

代码实现：

#include <stdio.h>
#include <stdlib.h>
#define Maxzie 10001

typedef struct Node {
    char ch[Maxzie];
    int top;
} Stack;

int main() {
    Stack s;
    s.top = -1;
    char c;
    // 读取输入，只存储括号字符
    while ((c = getchar()) != EOF && c != '\n') {
        if (c == '[' || c == ']' || c == '(' || c == ')') {
            s.ch[++s.top] = c;
        }
    }

    Stack t;
    t.top = -1;
    int valid = 1;
    // 遍历括号序列进行匹配
    for (int i = 0; i <= s.top; i++) {
        char ch = s.ch[i];
        if (ch == '[' || ch == '(') {
            t.ch[++t.top] = ch;          // 左括号入辅助栈
        } else {
            if (t.top == -1) {            // 栈空，无匹配左括号
                valid = 0;
                break;
            }
            char cht = t.ch[t.top];
            if ((ch == ')' && cht == '(') || (ch == ']' && cht == '[')) {
                t.top--;                  // 匹配成功，弹出
            } else {
                valid = 0;                 // 不匹配
                break;
            }
        }
    }

    // 最终辅助栈必须为空且过程中无错误
    if (valid && t.top == -1) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}