Python中链表的括号匹配（Valid Parentheses）操作

2023-04-11 00:00:00 匹配链表括号

链表的括号匹配操作可以使用栈（Stack）来实现。

首先，我们需要定义一个节点类，用于构建链表节点：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

接下来，我们定义一个栈类，用于保存左括号：

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

然后，我们可以使用链表模拟字符串的行为，逐个将字符作为链表节点插入到链表中：

def create_linked_list(s):
    dummy_node = ListNode(-1)  # 创建一个虚拟头节点
    cur = dummy_node  # 初始化当前节点
    for c in s:
        cur.next = ListNode(c)
        cur = cur.next
    return dummy_node.next  # 返回真实的头节点

接下来，我们可以使用栈来进行括号匹配。每当遇到左括号，就将其压入栈中；每当遇到右括号，就从栈中弹出一个左括号，并判断其是否匹配。如果栈为空或者弹出的左括号与当前的右括号不匹配，则说明括号不合法。最后，如果栈为空，则说明所有括号都匹配成功。

def is_valid_parentheses(s):
    head = create_linked_list(s)

    stack = Stack()
    while head:
        if head.val == '(' or head.val == '[' or head.val == '{':
            stack.push(head.val)
        elif head.val == ')':
            if stack.is_empty() or stack.pop() != '(':
                return False
        elif head.val == ']':
            if stack.is_empty() or stack.pop() != '[':
                return False
        elif head.val == '}':
            if stack.is_empty() or stack.pop() != '{':
                return False
        head = head.next

    return stack.is_empty()

最后，我们可以测试一下代码的正确性：

```python
print(is_valid_parentheses('pidancode()'))
print(is_valid_parentheses('(pidancode))'))
print(is_valid_parentheses('{pidancode[]}'))
print(is_valid_parentheses('(pidancode]'))
print(is_valid_parentheses('{pidancode'))

相关文章