LeetCode 20. 有效的括号（栈结构详解）

有效的括号问题详解

问题描述

给定一个只包含括号字符 '(', ')', '{', '}', '[', ']' 的字符串 s，判断该字符串是否有效。

有效字符串需要满足以下三个条件：

1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确的顺序闭合
3. 每个右括号都有一个对应的相同类型的左括号

问题背景与重要性

括号匹配是计算机科学中的基础问题，它出现在许多实际应用场景中。从编程语言的语法解析到数学表达式的计算，再到配置文件和数据格式（如 JSON、XML）的验证，括号匹配都扮演着重要角色。

问题分析

这是一个经典的栈应用问题。括号匹配需要遵循"后进先出"的原则，这与栈的特性完全吻合。

为什么选择栈结构？

括号匹配的核心要求是：最后打开的括号必须最先关闭。这与栈的"后进先出"(LIFO) 特性完美匹配。

想象一下日常生活中的例子：

• 我们穿脱衣服的顺序是最后穿上的衣服最先脱下
• 叠放盘子时，最后放上去的盘子最先被取用
• 文档编辑中的"撤销"功能也是后进先出的典型应用

括号匹配也是同样的道理。当我们遇到嵌套的括号时，最后打开的括号必须最先关闭，这正是栈数据结构的典型应用场景。

算法选择的原因

为什么使用栈而不是其他数据结构？

• 数组：需要维护额外的指针来跟踪最近打开的括号，实质上就是在模拟栈
• 队列：先进先出的特性与括号匹配的后进先出需求相反
• 链表：可以实现栈的功能，但代码复杂度较高

因此，直接使用栈是最自然和高效的选择。

算法思路

1. 初始化一个空栈
2. 遍历字符串中的每个字符
   • 如果是左括号（'(', '[', '{'），将其压入栈中
   • 如果是右括号（')', ']', '}'），则：
     • 检查栈是否为空（空栈表示没有与之匹配的左括号）
     • 弹出栈顶元素并与当前右括号比较是否匹配
     • 如果不匹配，则字符串无效
3. 遍历完成后
   • 如果栈为空，说明所有括号都正确匹配
   • 如果栈不为空，说明有未匹配的左括号，字符串无效

算法正确性证明

该算法的正确性可以通过循环不变式来证明：

• 初始化：栈为空，表示尚未遇到任何未匹配的左括号
• 保持：每次处理右括号时，都与最近未匹配的左括号（栈顶）进行比较，确保匹配的正确性
• 终止：遍历完成后，栈为空当且仅当所有括号都正确匹配

核心算法函数

bool isValid(char* s){
    // 处理空指针情况
    (s == ){
         ; 
    }
    
    ST st;
    STInit(&st); 
    
    (*s){ 
        
        (*s ==  || *s ==  || *s == ){ 
            STPush(&st, *s);
        }  { 
            
            (STEmpty(&st)){
                STDestroy(&st);
                 ;
            }
             top = STTop(&st); 
            STPop(&st); 
            
            
            ((top ==  && *s != ) || (top ==  && *s != ) || (top ==  && *s != )){
                STDestroy(&st);
                 ;
            }
        }
        s++; 
    }
    
    
     ret = STEmpty(&st);
    STDestroy(&st);
     ret;
}