使用堆栈在 python 中匹配括号

Question

我正在尝试使用堆栈来检查括号，但是下面的代码无法输出正确的结果；检查了好几遍，还是找不到错误；非常感谢任何提示或帮助！谢谢！

open_list = ["[","{","("] 
close_list = ["]","}",")"] 
def check(mystr):
    stack1 = []
    for i in mystr:
        if i in open_list:
            stack1.append(i)
        elif i in close_list:
            stack1.append(i)
    for i in stack1:
        index1 = open_list.index(i)
        expected_result = close_list[index1]
        if expected_result == stack1[-1]:
            stack1.remove(i)
            stack1.pop(-1)
        else:
            print(i)
            print(stack1, stack1, sep = '\n')
            return 'unbalanced'
    if len(stack1) == 0:
        return 'balanced'
    else:
        print(stack1)
        return 'unbalanced'

# example
list1 = '{a + [b - (c * [e / f] + g) - h] * i}'

# output
(
['[', '(', '[', ']', ')', ']']
['[', '(', '[', ']', ')', ']']
unbalanced

Answer 1

修改你正在迭代的列表将导致跳过元素，在检查函数的第二个循环的第一次迭代中你将有 expected_result == stack1[-1]，但在第二次迭代中i 是列表中的第二个值，现在修改后它将是 '(' 而不是 '['.

您可以通过仅将开放符号添加到堆栈中来简化逻辑，每次找到关闭符号时，您都比较以查看最后保存的开放符号是否是它的对，如果不是它是不平衡的。

def check(mystr):
    stack1 = []
    for i in mystr:
        if i in open_list:
            stack1.append(i)
        elif i in close_list:
            if not stack1 or stack1[-1] != open_list[close_list.index(i)]:
                return 'unbalanced'
            else:
                stack1.pop(-1)
    if len(stack1) == 0:
        return 'balanced'
    else:
        print(stack1)
        return 'unbalanced'

使用堆栈在 python 中匹配括号

parenthesis matching in python using stack

python

stack

singly-linked-list