用栈结构优雅破解括号匹配难题（力扣20题）

一、题目重新解读

给定一个仅包含 ('、')、'['、']'、'{'、'}' 的字符串，判断其是否有效。有效需满足：

1. 左括号必须与相同类型的右括号闭合（如 () 对应，[] 对应，{} 对应）；

2. 闭合顺序必须正确（先开的括号后闭）；

3. 不存在未匹配的括号。

二、解题思路与过程

1. 栈结构特性：栈“后进先出（LIFO）”的特性天然适配括号匹配——后出现的左括号需先被匹配。

2. 遍历策略：

    1.遇左括号直接压栈，记录“待匹配项”；

    2.遇右括号时：

    3.若栈空，说明右括号无对应左括号（如 ])），直接返回假；

    4.若栈顶左括号与当前右括号不匹配（如 ][），返回假；

    5.匹配成功则弹栈，继续下一字符。

3. 最终判断：遍历结束后，栈为空说明所有括号均匹配，否则存在剩余左括号（如 (]）。

三、代码与注释

class Solution {
public:
    // 判断字符是否为左括号的优雅舞步
    bool IsLift(char a) {
        return a == '(' || a == '[' || a == '{'; // 简洁的三重判断
    }

    bool isValid(string s) {
        if(s.size()&1) return false; // 奇数长度直接谢幕

        stack<char> s1; // 创建记忆栈
        for(int i=0; i<s.size(); i++) {
            if(IsLift(s[i])) {
                s1.push(s[i]); // 收集未完成的期待
            } else {
                if(s1.empty()) return false; // 空栈遇右括号必定失格
                
                // 检查栈顶元素是否与当前右括号共鸣
                if( (s1.top()=='(' && s[i]==')') || 
                    (s1.top()=='[' && s[i]==']') ||
                    (s1.top()=='{' && s[i]=='}') ) {
                    s1.pop(); // 成功配对则释放栈顶
                } else {
                    return false; // 不和谐音出现
                }
            }
        }
        return s1.empty(); // 最终校验所有期待都已满足
    }
};