5.3有效的括号（LC20

括号（LC20"/>

5.3有效的括号（LC20

算法：

题目中：左括号必须以正确的顺序闭合。意思是，最后出现的左括号（对应着栈中的最后一个元素），应该先找到对应的闭合符号（右括号）

比如:s="( [ ) ]"就是False，因为"("比"["先出现，对应地，"( [ "中最后的元素应该最先找到闭合符"]"，而 闭合符（就是右括号）先出现的是")"，这个时候就能判断False了

括号匹配是使用栈解决的经典问题。

由于栈结构的特殊性，非常适合做对称匹配类的题目。

首先要弄清楚，字符串里的括号不匹配有几种情况。

1.第一种情况：字符串里左方向的括号多余了 ，所以不匹配。

2.第二种情况：括号没有多余，但是 括号的类型没有匹配上。

3.第三种情况：字符串里右方向的括号多余了，所以不匹配。

怎么用栈来解决该问题？

举个例子：s="(","[","}",")"

遍历字符串中的符号，发现左括号时，往栈中push其对应的右符号；发现右括号时，往栈中pop与其一样的右括号

当遍历到"("，push“)”  //stack=")"

当遍历到"["，push"]"  //stack="]" , ")"

当遍历到"}"，push“}”  //stack=“}”, "]" , ")"

当遍历到")", pop ")"  //stack=“}”, "]" 

发现stack非空，说明括号无效。

总的代码思路如下（遍历s中的符号item）：

1.如果 `item` 是一个开放符号（‘(’, ‘[’, ‘{’），则将相应的闭合符号压入栈中。

2.如果 `item` 是一个闭合符号（‘)’, ‘]’, ‘}’），则检查栈是否为空，或者栈顶元素（最后一个元素）与 `item` 不相等。

• 栈为空：说明没有右括号了，肯定不对了
• 栈顶元素（最后一个元素）与 `item` 不相等：说明最近的需要的闭合符号不对（和示例一样）
• 如果以上任一条件为真，则意味着闭合符号不平衡，函数返回 `False`。

3.如果 `item` 是一个闭合符号，并且它与栈顶元素匹配，那么从栈中弹出顶部元素，表示开放符号和闭合符号是平衡匹配的。

4.在遍历完 `s` 中的所有字符后，如果栈为空，则表示所有的开放符号都已经匹配并弹出，函数返回 `True`。否则，如果栈不为空，则表示存在未匹配的开放符号，函数返回 `False`。

调试过程：

class Solution:def isValid(self, s: str) -> bool:stack = []for item in s:#如果s的长度为奇数，必然不符合，可以做个简单判断剪枝，节省时间if len(s)%2 != 0:return Falseelif item == "(":stack.append(")")elif item == "[":stack.append("]")elif item == "{":stack.append("}")#如果输入的不是以上三种左括号，那只能是右括号了#如果是右括号，正确的s对应的stack中应该存在该右括号了（刚刚append了）#如果此时stack为空，或者栈顶非距离最近的左括号的闭合符号，那就Falseelif not stack or item != stack[-1]:#注意：应该先判非空再判item != stack[-1]，因为若stack为空，stack[-1]不存在，判断时就会报错return Falseelse:stack.pop()return True if stack == None else False

原因：最后返回语句写得不对。栈为空应该用“stack == []”或者“len(stack)==0”表示。

在Python中，`None` 表示一个空对象，而 `[]` 表示一个空列表。在这段代码中，我们使用一个列表来模拟栈的数据结构。当栈为空时，我们希望栈对象 `stack` 的值是一个空列表 `[]`。

当使用 `stack == None` 进行判断时，它会检查栈对象 `stack` 是否是 `None`，而不是一个空列表。因此，如果栈为空，但是栈对象 `stack` 的值是 `None`，那么判断结果就会是错误的。

正确代码：

class Solution:def isValid(self, s: str) -> bool:stack = []for item in s:#如果s的长度为奇数，必然不符合，可以做个简单判断剪枝，节省时间if len(s)%2 != 0:return Falseelif item == "(":stack.append(")")elif item == "[":stack.append("]")elif item == "{":stack.append("}")#如果输入的不是以上三种左括号，那只能是右括号了#如果是右括号，正确的s对应的stack中应该存在该右括号了（刚刚append了）#如果此时stack为空，或者栈顶非距离最近的左括号的闭合符号，那就Falseelif not stack or item != stack[-1]:#注意：应该先判非空再判item != stack[-1]，因为若stack为空，stack[-1]不存在，判断时就会报错return Falseelse:stack.pop()return True if stack == [] else False

时间空间复杂度：

• 时间复杂度: O(n)
• 空间复杂度: O(n)