为何相邻字符无法判断括号有效？
摘要：一、这题表面简单，但很容易想偏 今天这题是 LeetCode 20：有效的括号。 题目给你一个只包含下面六种字符的字符串： ( ) [ ] { } 你要判断这个字符串是不是“有效”。 有效的意思是： 左括号必须用相同类型的右括号闭合 左括号
一、这题表面简单，但很容易想偏
今天这题是 LeetCode 20：有效的括号。
题目给你一个只包含下面六种字符的字符串：
(
)
[
]
{
}
你要判断这个字符串是不是“有效”。
有效的意思是：
左括号必须用相同类型的右括号闭合
左括号必须按正确顺序闭合
每个右括号都要有对应的左括号
比如：
示例 1
s = "()"
输出：
True
示例 2
s = "()[]{}"
输出：
True
示例 3
s = "(]"
输出：
False
这题一开始看着像“括号配对题”，好像不难。
但很多初学者第一次写，都会很自然地走到一个错误思路上：
看当前左括号后面是不是紧跟着对应的右括号
这个想法很自然，但其实不对。
二、为什么“只看相邻两个字符”会错
一开始最容易想到的写法，大概是这样：
if s[i] == "(" and s[i + 1] != ")":
return False
意思是：
如果当前是 (，那它后面必须立刻跟着 )
但问题是，这题不是只判断“相邻两个字符能不能配对”，而是判断整个字符串的嵌套结构对不对。
比如这个字符串：
s = "([])"
它其实是有效的。
因为：
最外层 ( 和 ) 配对
中间 [ 和 ] 配对
可如果你只看相邻字符：
第一个字符是 (
它后面紧跟着的是 [，不是 )
你就会误判成 False
可实际上它明明是对的。
所以这题最大的问题就在这里：
有些括号虽然匹配，但它们不一定挨在一起。
也就是说，这题不能只看 s[i] 和 s[i+1]。
三、这题真正考的是什么
这题真正想考的是：
每当你遇到一个右括号，它应该和“最近的那个还没匹配的左括号”配对。
注意这句话里的关键词：
最近的、还没匹配的左括号
这就是一个典型的“后进先出”问题。
也就是说：
后出现的左括号
要先被匹配掉
这正是 栈（stack） 的特点。
四、先别怕，栈没有那么玄乎
“栈”这个词听起来有点像数据结构课上的概念，但你可以先把它想得很简单：
它就像一摞盘子。
新放上去的盘子在最上面
你每次拿的时候，也只能先拿最上面的盘子
所以它的特点就是：
后放进去的，先拿出来
这就叫：
后进先出（LIFO，Last In First Out）
在 Python 里，我们通常直接用列表来模拟栈：
stack = []
入栈
stack.append("(")
出栈
stack.pop()
比如：
stack = []
stack.append("(")
stack.append("[")
print(stack)
输出：
['(', '[']
然后：
stack.pop()
会先弹出 [，因为它是最后放进去的。
这就很适合拿来处理括号问题。
五、这题的核心思路
我们从左到右遍历整个字符串。
遇到左括号
就先把它放进栈里。
比如：
遇到 (，入栈
遇到 [，入栈
遇到 {，入栈
遇到右括号
就去看栈顶的左括号能不能和它匹配。
比如：
遇到 )，栈顶必须是 (
遇到 ]，栈顶必须是 [
遇到 }，栈顶必须是 {
如果不能匹配，直接返回 False。
最后如果整个字符串遍历完了，栈也正好空了，说明所有括号都匹配成功，返回 True。
六、最适合初学者理解的写法
我先给出一版最容易看懂的代码：
def is_valid(s):
"""
:type s: str
:rtype: bool
"""
stack = []
for ch in s:
if ch == '(' or ch == '[' or ch == '{':
stack.append(ch)
else:
if not stack:
return False
top = stack.pop()
if ch == ')' and top != '(':
return False
if ch == ']' and top != '[':
return False
if ch == '}' and top != '{':
return False
return len(stack) == 0
你先别急着背，下面我们慢慢拆开讲。