括号匹配

括号迷宫大冒险，栈来当裁判！

📖知识引入

📥左括号入栈

扫到左括号( [ {就压进栈，等待未来的另一半

📤右括号配对

扫到右括号就查栈顶：类型相同则弹出，不同或栈空即失败

🏁终判条件

扫描结束后栈空说明全部配对成功，栈里剩括号就是缺右半

🧠思维精髓

最近的左括号最先被配对，天然的后进先出，非栈莫属

💡

三种括号可用字符串()[]{}统一处理：char配对判断写个函数，代码更清爽

🔍括号匹配经典实现

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);            // 左括号入栈
        } else {
            if (st.empty()) return false;      // 没有左括号可配
            char t = st.top();
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{'))
                return false;                  // 类型不匹配
            st.pop();            // 配对成功，弹出
        }
    }
    return st.empty();  // 栈空才全配对
}

左进右出栈裁判，配对成功空栈收官

🎯小测验

第1题：扫描到右括号时若栈为空，说明什么？

第2题：字符串“([”扫描结束后栈的状态是？

第3题：括号匹配问题本质利用了栈的什么特性？

📝本课知识点

✓左括号进栈，右括号查顶
✓扫描完栈空才算匹配
✓括号匹配是栈的头号应用

第15课完成！继续探索下一课吧 🚀

📚

上一课

第14课

下一课

第16课

📚