时间戳

首页 > 解决方案 > 为什么配对嵌套分析的堆栈经常是空的？

python - 为什么配对嵌套分析的堆栈经常是空的？

问题描述

以下是我尝试检查平衡括号的代码。

def is_matched(expression):
    opening = tuple('({[');
    closing = tuple(')}]');
    mapping = dict(zip(opening,closing));
    queue = [];

    for letter in expression : 
        if letter in opening : 
            queue.append(mapping[letter]);
        elif letter in closing : 
            if (not queue) or (letter != queue.pop()) :
                return False;
    return not queue;

ip = input();
if is_matched(ip):
    print ("Valid");
else:
    print("Invalid");

我的问题是为什么queue列表要[]为 for 循环中输入参数中的每个字母声明？
它不应该在循环中附加每个字典映射吗？

标签： pythonlistfor-loop

解决方案

该代码不会“附加每个字典映射”。
它只为在 中找到的字母附加任何内容opening。
附加的是来自closing.
它通常会将队列返回到[]，因为它也会执行很多pop()，
这会删除一封信。
当pop()来自输入的当前字母与最后附加的字母匹配时发生，
即当最近打开的对被关闭时。例如，队列[]位于以下输入的这些位置：

vvv     vvv     vvv     vvv         vvvvv
abc(xxxx)fg[....]hi{llll}gh(--[ff]++)gggg

请注意，正如评论中也提到的那样，queue这里的行为更像是一个堆栈，这是正确的。

推荐阅读