Validate Parentheses 括号匹配校验：Python 栈算法实战指南（cosmos 项目）

教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载导读本文基于 cosmos 仓库中的 Validate Parentheses 文档 与其配套 Python 实现系统讲解如何判断一个仅含( ) [ ] { }三类括号的字符串是否合法有效。读者将掌握基于栈Stack的括号匹配校验算法原理、边界条件与复杂度分析并了解该算法在仓库数据结构模块中的多种语言对照实现可直接复制运行用于编码面试与日常工具开发。问题定义什么是合法的括号字符串原文档明确给出了本题的核心约束给定一个只包含字符( ) [ ] { }的字符串判断输入字符串是否有效。所谓有效valid指的是字符串中的括号必须满足正确的成对匹配与嵌套顺序每个左括号都必须被一个同类型的右括号关闭并且关闭的顺序必须符合后进先出LIFO的嵌套规则——即最近打开的括号必须最先被关闭。原文档给出的两个经典示例([(){()}()])→Valid所有括号成对出现且嵌套顺序正确({[(])}({}))→Invalid存在交叉嵌套{ [ ( ]中[被]关闭前(却先被)关闭顺序错乱从这两个示例可以看出括号数量成对并不能保证字符串合法类型匹配与嵌套次序才是判定核心。核心算法利用栈的 LIFO 特性进行匹配本仓库的 validate-parentheses.py 给出了完整可运行的解法。该算法本质上是用列表模拟栈遇到左括号入栈push遇到右括号出栈pop并校验配对。源代码如下def validateParentheses(parentheses): queue[] for ch in parentheses: #enqueue for open-character if ch in ((,{,[): queue.append(ch) #dequeue for close-character elif ch in (),},]): pre_ch queue.pop() #Validate for matching pair open and close character if ( ch) and pre_ch!( ) or ( ch] and pre_ch![ ) or ( ch} and pre_ch!{ ) : return False #any different character else: return False #any remain character if (len(queue) 0): return False #Success return True parentheses input(Enter a string to validate:) print(validateParentheses(parentheses))算法逐字符扫描字符串可分为四个处理分支左括号入栈字符为({[之一时append到列表尾部即栈顶右括号出栈配对字符为)}]之一时先pop出栈顶元素pre_ch再校验三者之一是否成立)必须对应(、]必须对应[、}必须对应{任一不匹配立即返回False非法字符拦截出现括号以外的任何字符直接返回False原文档限定输入仅含括号此分支用于防御非法输入收尾检查遍历结束后若栈内仍有剩余左括号len(queue) 0说明存在未闭合的括号返回False否则返回True。边界条件与判定陷阱该算法的正确性建立在三个关键边界处理上也是面试中常被追问的考察点右括号多余栈为空时 pop例如输入())处理到最后一个)时栈已空。当前实现中queue.pop()对空列表会抛出IndexError。原文档虽未显式讨论该情形但这是此类题目的标准边界。仓库 balanced_expression.py 给出了更稳健的写法用try/except IndexError捕获空栈弹出并返回False可作为本实现的强化参考左括号多余遍历结束栈非空例如((或(()结束时栈内仍有残留第 1718 行的len(queue) 0判断专门处理此情况类型错配例如(]或{[)}虽然数量成对但配对校验第 11 行会立即返回False这正是原文档第二个示例({[(])}({}))被判为 Invalid 的原因。时间复杂度与空间复杂度由于每个字符恰好被扫描一次且每次入栈/出栈操作均为 O(1)时间复杂度O(n)其中 n 为字符串长度空间复杂度O(n)最坏情况下如(((((所有字符都入栈。仓库源码纵深从括号校验到通用栈数据结构本算法是栈Stack这一 LIFO 抽象数据类型的经典应用场景。仓库 data_structures/src/stack/README.md 对栈的定义与操作做了系统说明栈支持Push()入栈、Pop()出栈、Peek()查看栈顶与isEmpty()判空四类核心操作且这些操作的时间复杂度均为 O(1)。围绕同一括号平衡/合法性问题仓库在 balanced_expression 目录下提供了多语言对照实现适合横向对比学习C 实现balanced_expression.c手动用链表构建栈结构体演示push、pop、peek、empty四个底层操作的完整实现并加入len % 2 ! 0的奇偶长度快速剪枝C 实现balanced_expression.cpp直接使用标准库std::stackchar逻辑与本文 Python 版几乎一一对应可作算法思路的对照阅读Java 实现balanced_expression.java在遇到右括号时先检查stack.empty()再 pop显式规避了空栈问题是该边界处理的另一经典写法。对比可见本文主角 validate-parentheses.py 用 Python 列表append/pop天然模拟栈顶操作代码简洁而 C/Java 版本则暴露了更多底层细节如链表节点分配、判空时机两者结合阅读可加深对栈这一数据结构本质的理解。运行与验证在 Python 3 环境下直接运行即可交互式验证python3 validate-parentheses.py程序通过input()提示Enter a string to validate:输入后打印True或False。可依次验证以下用例输入字符串预期输出说明([(){()}()])True原文档示例合法({[(])}({}))False原文档示例交叉嵌套非法()True最简单合法情形((False左括号多余())False抛 IndexError右括号多余可参考 balanced_expression.py 的 try/except 加固(]False类型错配小结Validate Parentheses 是栈数据结构最直观、最高频的入门应用题其解法固定、边界清晰、复杂度分析简单但覆盖了入栈出栈 配对校验 空栈/残留处理三大要点。本文以 validate-parentheses.py 为主线完整还原了解法并通过仓库 balanced_expression 的多语言实现补充了边界加固思路与底层数据结构细节读者可将该模板直接用于编码面试或编译器语法检查等真实场景。赞分享教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载相关推荐LeetCode 0020 Valid Parentheses基于栈的括号匹配校验算法全解析多语言实现LeetCode 0020 Valid Parentheses基于栈的括号匹配校验算法全解析多语言实现 导读 Valid Parentheses 有效的示例工程教程Less.js 变量指南用变量与 import 快速搭建可维护的 CSS 体系Less.js 变量指南用变量与 import 快速搭建可维护的 CSS 体系 Less.js 是一款动态样式表语言The dynamic styleshe前端开发工具LeetCode-Go 题解精讲20. Valid Parentheses 括号匹配的栈实现与测试验证LeetCode Go 题解精讲20. Valid Parentheses 括号匹配的栈实现与测试验证 本篇技术指南以 LeetCode Go 仓库中 002示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考