题解 | 括号的匹配

真是杂鱼呢~怎么这题都不会写阿❤。

作为栈专栏的最后一题只要做了前一题就知道这题怎么写吧,这题最优解应该是 栈 + 嵌套顺序校验

做法上如果是左括号就压栈,如果是右括号就判断是否 栈空 和 是否对应了左括号 如果不是栈空且对应了就出栈。

但是这题要求了括号大小顺序也必须遵循,而这四个括号的左括号（只压栈左括号）的ASCII值也并不是正好符合题目对应的顺序的。所以我们可以通过写一个转换函数把{转换成4然后[转换成3以此类,这样就能满足题目按照顺序的括号了,同时我们可以转换右括号也避免写太多字符,比如{是4对应右括号是-4这样后续的左右括号对应也会很方便检验。

#include <iostream>
#include <vector>
using namespace std;

int transform(char c) {
    if (c == '{') return 4;
    if (c == '[') return 3;
    if (c == '(') return 2;
    if (c == '<') return 1;
    if (c == '}') return -4;
    if (c == ']') return -3;
    if (c == ')') return -2;
    if (c == '>') return -1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        if (s.size() % 2 != 0) {
            cout << "NO\n";
            continue;
        }

        vector<int> stac;
        bool valid = true;
        for (char c : s) {
            int num = transform(c);
            if (num > 0) {
                // 左括号：检查是否违反嵌套顺序（不能比栈顶更大）
                if (!stac.empty() && num > stac.back()) {
                    valid = false;
                    break;
                }
                stac.push_back(num);
            } else {
                if (stac.empty() || stac.back() != -num) {
                    valid = false;
                    break;
                }
                stac.pop_back();
            }
        }

        if (valid && stac.empty()) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}