题解 | 括号配对问题

#include <iostream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

bool isValidBracketSequence(const string& s) {
    vector<char> brackets;

    // 1. 提取所有括号字符
    for (char c : s) {
        if (c == '(' || c == ')' || c == '[' || c == ']') {
            brackets.push_back(c);
        }
    }

    stack<char> stk;
    // 2. 检查括号序列是否合法
    for (char bracket : brackets) {
        if (bracket == '(' || bracket == '[') {
            // 如果是左括号，压入栈
            stk.push(bracket);
        } else {
            // 如果是右括号
            if (stk.empty()) {
                // 栈为空，但遇到了右括号，说明没有匹配的左括号
                return false;
            }

            char top = stk.top();
            stk.pop();

            // 检查括号是否匹配
            if ((bracket == ')' && top != '(') ||
                    (bracket == ']' && top != '[')) {
                return false;
            }
        }
    }

    // 3. 遍历结束后，栈必须为空才是完全匹配
    return stk.empty();
}

int main() {
    string input;
    getline(cin, input);

    bool result = isValidBracketSequence(input);
    cout << (result ? "true" : "false") << endl;

    return 0;
}