前言
🍀作者简介：被吉师散养、喜欢前端、学过后端、练过CTF、玩过DOS、不喜欢java的不知名学生。
栈的应用：简单括号匹配
首先说到括号，就是那种数学运算或者是逻辑运算中非常简单的括号
这玩意的使用呢，必须遵循某种规则，即“平衡”
说白了，就是括号必须得是一对，重点不在前面的“一”上，而是在“对”上
明白了吧，有开就有闭，有左就有右
那么我们应该如何构造括号匹配识别算法
首先遇到一串带有多个括号的代码，我们应先将无关的部分摘除掉，只留下括号，来分析逻辑
接下来我们从左到右来分析
最先遇到的是左侧第一个括号，那么它所对应的，是右侧最后一个括号，这也正好符合了我们之前说的
次序反转的识别，这正巧符合栈的特性
接下来呢，我们来看一道题
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 示例 1： 输入：s = "()" 输出：true 示例 2： 输入：s = "()[]{}" 输出：true 示例 3： 输入：s = "(]" 输出：false 提示： 1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成
直接分析代码
作者：shen-du-xue-xi-s
链接：https://leetcode.cn/problems/valid-parentheses/solution/by-shen-du-xue-xi-s-q3ul/
来源：力扣（LeetCode）
class Solution: def isValid(self, s: str) -> bool: #用字典来存储括号对，键是左括号，值是右括号 dic = { '(':')', '[':']', '{': '}' } #构造辅助栈 stack = [] #开始遍历每一个括号，只将左括号入栈，当下一次入栈的是 栈顶元素相对应 的右括号时，把栈顶元素出栈；如果不是，则直接返回False for i in s: #如果是左括号，则入栈 if i in dic: stack.append(i) #如果是右括号且栈不为空，判断栈顶元素(stack[-1])是否与当前要入栈的元素（i）相匹配 elif stack: #如果匹配，把栈顶元素出栈 if dic[ stack[-1] ] == i: stack.pop() #如果不匹配，则直接返回False else: return False #如果右括号且栈为空，肯定不匹配，直接返回False else: return False #如果最后栈中元素为空，说明为有效括号，返回True if len(stack) == 0: return True #否则返回False else: return False
来看下这串代码
def isValid(self, s: str) -> bool:
这个其实是python3的新特性，传入的形参为s，而“:”后面的str为注释
之所以叫做注释，是因为即使这玩意写的是str，还是能传入一个int进去且不报错(前提是代码内部能够正确处理，而后面的bool，则是对return返回值的注释
思路大体就是，在字符串中选择匹配的括号，先将左括号添加至栈顶，然后选择右括号
如果栈不空，则这一对括号成功匹配
如若在匹配到右括号时，栈为空，则说明这右括号是多余的，不符合平衡原则
如若在全部选择完之后发现栈不空，里面还有剩余的左括号，则说明这左括号是多余的，不符合平衡原则
当然，在HTML/XML这种层次结构化文档的校验，操作，也可以通过栈来实现
