括号验证程序中栈的入栈出栈操作及字典匹配栈机制问询

首先，先把你提供的代码完整展示出来，方便咱们对照分析：

class py_solution: 
    def is_valid_parenthese(self, str1): 
        stack=[] 
        pchar = {"(": ")", "{": "}", "[": "]"} 
        for parenthese in str1: 
            if parenthese in pchar: 
                stack.append(parenthese) 
            elif len(stack) == 0 or pchar[stack.pop()] != parenthese: 
                return False 
        return len(stack) == 0 
st=raw_input("Enter string of parenthesis") 
print(py_solution().is_valid_parenthese(st))

一、迭代过程中栈的push和pop操作执行逻辑 #

咱们拿一个合法的输入例子"({[]})"来一步步拆解每一次循环里栈的变化：

1. 第一个字符(：它是字典pchar的键，所以执行stack.append("(")，此时栈内容为["("]。
2. 第二个字符{：同样是字典的键，执行stack.append("{")，栈内容变为["(", "{"]。
3. 第三个字符[：还是字典的键，执行stack.append("[")，栈内容变为["(", "{", "["]。
4. 第四个字符]：它不在字典的键里，进入第二个分支。首先检查栈不为空（此时栈长度是3），然后执行stack.pop()弹出栈顶的[，用字典pchar取出对应的值]，和当前字符]对比，两者相等，继续循环，此时栈内容变为["(", "{"]。
5. 第五个字符}：不在字典键里，栈不为空，弹出栈顶的{，字典中对应的值是}，和当前字符匹配，继续循环，栈内容变为["("]。
6. 第六个字符)：不在字典键里，栈不为空，弹出栈顶的(，字典中对应的值是)，和当前字符匹配，继续循环，栈内容变为[]。
7. 循环结束：检查栈长度为0，返回True，说明括号合法。

如果遇到非法的情况，比如输入"([)]"：

• 前两个字符(和[依次入栈，栈是["(", "["]。
• 第三个字符)：弹出栈顶的[，字典中[对应的值是]，和)不相等，直接返回False，程序终止。

还有一种情况是输入只有右括号，比如")"：

• 第一个字符不在字典键里，此时栈长度为0，直接返回False。

二、左括号为键、右括号为值的字典在栈中的工作方式 #

这个字典pchar的设计非常巧妙，核心作用就是快速匹配对应括号：

• 当遇到左括号（字典的键）时，我们只需要把它压入栈中，不用管它对应的右括号是什么——因为我们要等后续出现的右括号来“配对”。
• 当遇到右括号时，我们需要确认它和最近压入栈的左括号是一对：此时弹出栈顶的左括号，用字典直接取出它对应的右括号，和当前的右括号对比。如果相等，说明配对成功；不相等或者栈为空（没有左括号可以配对），就说明括号不合法。

这种设计的好处是：

• 查找效率高：字典的键查找是O(1)时间复杂度，比用多个if-elif判断要高效得多。
• 代码更简洁：不用写一堆判断左括号对应哪个右括号的逻辑，直接通过字典映射就能完成配对检查。

内容的提问来源于stack exchange，提问作者midhun pc