Python栈的应用：括号序列的匹配问题

2023-04-10 00:00:00 序列匹配括号

栈是计算机科学中一个重要的数据结构，它遵循先进后出的原则。在栈中，只有栈顶元素可以被访问，因此栈被称为一种“后进先出”的数据结构。Python有内置的列表结构可以用作栈。

括号序列的匹配问题是在计算机科学中经常遇到的问题之一。在这个问题中，我们需要判断一个给定的括号序列是否是匹配的。如果是匹配的，那么每个左括号都应该有与之匹配的右括号。例如，{[()]}是一个匹配的括号序列，而{[(])}则不是。

下面是使用Python栈实现括号序列匹配的示例代码：

def is_matching_parenthesis(string):
    stack = []
    for char in string:
        if char in ["(", "{", "["]:
            stack.append(char)
        else:
            if not stack:
                return False
            current_char = stack.pop()
            if current_char == "(":
                if char != ")":
                    return False
            if current_char == "{":
                if char != "}":
                    return False
            if current_char == "[":
                if char != "]":
                    return False
    if stack:
        return False
    return True

该代码首先创建一个空栈，然后遍历给定的字符串中的每个字符。如果遇到一个左括号，就将其压入栈中。如果遇到一个右括号，就从栈中弹出栈顶元素，并检查是否与右括号匹配。如果不匹配，返回False。

如果最后栈中还有元素，说明左括号数量多于右括号数量，也返回False。否则，返回True，说明给定的括号序列是匹配的。

以下是代码的具体演示：

>>> is_matching_parenthesis("pidancode")
True
>>> is_matching_parenthesis("pidancode}")
False
>>> is_matching_parenthesis("({[]})")
True
>>> is_matching_parenthesis("{{}}[](")
False

在以上示例中，第一个字符串是匹配的，因为它不包含任何括号。第二个字符串不是匹配的，因为它包含一个右括号，但没有左括号与之匹配。第三个字符串是匹配的，因为它包含三种类型的括号，并且它们都正确匹配。第四个字符串不是匹配的，因为它只包含左括号，没有右括号与之匹配，因此栈中仍有元素。

相关文章