使用栈实现括号匹配算法时遭遇TypeError错误求助

我正在尝试编写一个用栈检查表达式括号是否匹配的算法，但一直报错。以下是我的匹配函数实现：

def is_matched(expression):
    left_bracket = "[({"
    right_bracket = "])}"
    my_stack = Stack(len(expression))
    # our solution methodology is to go through the expression and push all of the the open brackets onto the stack and then
    # with the closing brackets - each time we encounter a closing bracket we will pop the stack and compare
    for character in expression:
        if character in left_bracket:
            my_stack.push(character)
        elif character in right_bracket:
            # first check to see that the stack is not empty i.e we actually have some opneing brackets in the expression
            if my_stack.is_empty():
                return False
                # now we need to check that the type of braket we pop is the equivalent of it's closing bracket in the expression
            if right_bracket.index(character) != left_bracket.index(my_stack.pop):
                return False
    return my_stack.is_empty()

print(is_matched("()"))

报错信息如下：

if right_bracket.index(character) != left_bracket.index(my_stack.pop):
TypeError: expected a string or other character buffer object
python-BaseException

我的栈类实现代码如下：

class Stack:
    def __init__(self, capacity):
        """Builds a stack with given capacity > 0."""
        if capacity <= 0:
            raise Exception("The capacity must be positive")
        self.the_array = [None] * capacity
        self.top = -1  # the index of the top element

    def size(self):
        """Returns the size, i.e. the number
        of elements in the container."""
        return self.top + 1

    def is_empty(self):
        """Returns True if and only if the container is empty."""
        return self.size() == 0

    def is_full(self):
        """Returns True if and only if the container is full."""
        return self.size() >= len(self.the_array)

    def push(self, item):
        """Places the given item at the top of the stack
        if there is capacity, or raises an Exception."""
        if self.is_full():
            raise Exception("The stack is full")
        self.top += 1
        self.the_array[self.top] = item

    def pop(self):
        """Removes and returns the top element of the stack,
        or raises an Exception if there is none."""
        if self.is_empty():
            raise Exception("The stack is empty")
        item = self.the_array[self.top]
        # removes a reference to this item,
        # helps with memory management and debugging
        self.the_array[self.top] = None
        self.top -= 1
        return item

    def reset(self):
        """Removes all elements from the container."""
        while not self.is_empty():
            self.pop()
        assert (self.is_empty)

按照预期，第二次迭代时应弹出栈元素，判断左右括号的索引是否一致，最后检测栈为空并返回True，但实际却抛出了TypeError错误，希望得到帮助。

问题分析与修复 #

核心错误原因 #

报错的直接原因是调用栈的pop方法时没有加括号：my_stack.pop是引用方法对象本身，而不是执行方法获取返回的栈顶字符。left_bracket.index()需要传入字符串/字符类型参数，传入方法对象自然触发TypeError。

修复代码 #

只需要将my_stack.pop修改为my_stack.pop()即可，修改后的关键代码如下：

elif character in right_bracket:
    if my_stack.is_empty():
        return False
    # 加上括号调用pop方法，获取栈顶元素
    if right_bracket.index(character) != left_bracket.index(my_stack.pop()):
        return False

额外优化建议 #

1. 可以提前用字典存储括号映射关系，避免每次调用index遍历字符串，提升效率：

bracket_map = {')': '(', ']': '[', '}': '{'}
# 后续判断时直接使用：
if bracket_map[character] != my_stack.pop():
    return False

2. 栈的reset方法中，assert (self.is_empty)应改为assert self.is_empty()，否则是检查方法对象是否为真，而非调用方法判断栈是否为空。

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