Python 堆栈（有效括号）

Question

给定一个仅包含字符“(”、“)”、“{”、“}”、“[”和“]”的字符串 s，确定输入字符串是否有效。

如果满足以下条件，则输入字符串有效：

左括号必须由相同类型的括号闭合。左括号必须以正确的顺序闭合。

编辑：更新代码如下：

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        if len(s)<2:
            return False
        for ch in s:
            if ch == "(" or ch == "{" or ch == "[":
                stack.append(ch)
            elif ch == ")":
                if not stack or stack.pop() != "(":
                    return False
                
            elif ch == "]":
                if not stack or stack.pop() != "[":
                    return False
                
            elif ch == "}":
                if not stack == True or stack.pop() != "{":
                    return False
                
        
        return True

我想做的是创建一个堆栈。所以任何左括号都附加在里面。当程序看到右括号时，它必须匹配类型。如果是，它会从括号中弹出并继续循环。但是，我得到了这个错误：

IndexError: pop from empty list
    stack.pop()
Line 13 in isValid (Solution.py)
    ret = Solution().isValid(param_1)
Line 48 in _driver (Solution.py)
    _driver()
Line 59 in <module> (Solution.py)

不确定这里的错误是什么，我们将不胜感激。输入为“()[]{}”

Answer 1

每个不是左括号的字符弹出两次：一次在 if 条件下，然后再次 else。例如，对于 "()" 的输入：

第 0 个字符："(" 被压入堆栈。堆栈有 1 个元素。
第 1 个字符："(" 从堆栈中弹出。堆栈有 0 个元素。 "(" 与"(" 相同，因此执行else。 stack.pop() 引发显示的异常。

事实上，如果括号匹配，则无需执行任何其他操作。只需删除 else: stack.pop() 子句。

顺便说一句，如果字符不是左括号，您还需要确保堆栈不为空，并且 return False 如果是，则考虑 ")" 这样的示例或 "[{}()]]"，否则 stack.pop() 在遇到不匹配的右括号时将再次失败。

另外，if s[i] == ("(" or "{" or "["): 并没有按照您的想法行事。 "(" 是真实的，"{" 也是真实的； X or Y returns 如果第一个元素为真，则第二个元素为 left-associative。因此，"(" or "{" or "["的结果是"["，为真，所以这个if等价于if s[i] == "["。您想改写其中之一：

if s[i] == "(" or s[i] == "{" or s[i] == "[":
if s[i] in ["(", "{", "["]:
if s[i] in {"(", "{", "["}:
if s[i] in "({[":

然后 if not stack: return False 解决前一点。

第三点：range(start, end) 开始于 start 并在之前 end 结束，因此要遍历字符串中所有字符的索引，你需要 range(0, len(s))。例如。如果字符串是 "([])"，那么 range(0, len(s)-1) 就是 range(0, 3)，这将产生索引 0、1 和 2 — 所以最后一个字符， s[3]，永远不会被检查。因此，-1 是有害的，应该删除。或者，比这更好，因为除了访问该索引处的字符之外，您从不使用索引，所以最好完全跳过索引的想法，并直接迭代字符：for ch in s:

还有一个小问题：所有的右括号检查都是互斥的，所以使用 elif insted 第二个和第三个 if 会稍微提高性能。如果您有一个查找指令告诉您哪个左括号对应于每个右括号，您也可以将所有案例合并为一个。

Python 堆栈（有效括号）

Python Stack (Valid Parentheses)

python

stack