C++ 第41题：std::stack 栈适配器应用：符号括号匹配合法性校验

题目

编写程序，利用 std::stack<char> 容器适配器校验包含圆括号 ()、方括号 []、花括号 {} 的字符串括号配对是否合法。重点处理三种典型非法边界：右括号与栈顶左括号类型不匹配、右括号出现时栈已空（右侧多出）、扫描结束后栈内仍有残留左括号（左侧多出）。

输入格式：无需外部输入（内置四组括号测试串）。

输出格式：输出该括号串合法性判定的布尔结论；若非法明确指出错误原因。

数据范围与约定：字符串长度 <code>≤ 10^5</code>。

思路与算法

1. 后进先出 LIFO 契合性
括号匹配本质是就近消解：后出现的左括号必须先被对应的右括号闭合，与栈（Stack）的 LIFO 特征完美契合。

2. 适配器机制
std::stack 本身不是独立容器，而是容器适配器（Container Adapter），默认由 std::deque 在底层支撑，提供 push()、pop()、top() 与 empty() 接口。

3. 映射消解表
使用辅助函数判定左右配对，遇到左括号压栈，遇到右括号先判空再比对弹栈，最后校验 stack.empty() 是否完全清空。

完整程序

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

bool isMatchingPair(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

bool isValidParentheses(const std::string& s) {
    std::stack<char> st;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch); // 左括号压栈
        } else if (ch == ')' || ch == ']' || ch == '}') {
            // 边界 1：右括号出现但栈已空，说明右括号多余
            if (st.empty()) {
                return false;
            }
            // 边界 2：右括号与最近的左括号不匹配
            if (!isMatchingPair(st.top(), ch)) {
                return false;
            }
            st.pop(); // 成功匹配消解
        }
    }

    // 边界 3：遍历完后栈中不能有未闭合的左括号残留
    return st.empty();
}

int main() {
    std::string s1 = "{[()]}";
    std::string s2 = "{[(])}";
    std::string s3 = "((())";
    std::string s4 = "()[]{}";

    std::cout << s1 << " -> " << (isValidParentheses(s1) ? "合法" : "非法") << "\n";
    std::cout << s2 << " -> " << (isValidParentheses(s2) ? "合法" : "非法") << "\n";
    std::cout << s3 << " -> " << (isValidParentheses(s3) ? "合法" : "非法") << "\n";
    std::cout << s4 << " -> " << (isValidParentheses(s4) ? "合法" : "非法") << "\n";

    return 0;
}

运行示例

输出：

{[()]} -> 合法
{[(])} -> 非法
((()) -> 非法
()[]{} -> 合法