撤消/重做使用堆栈实现

Question

我想使用堆栈实现撤消-重做功能。当用户按下 Ctrl+Z 时，最后一个节点将从屏幕上删除。当用户再次按下 Ctrl+Z 时，“last.last”节点将从屏幕上删除，如果他按下 Ctrl+Y，则最后删除的节点将再次显示在屏幕上。

下面是我的代码：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None


class Stack:
    def __init__(self):
        self.pointer = None

    def push(self, x):
        if not isinstance(x, Node):
            x = Node(x)
        if self.is_empty():
            self.pointer = x

            undo_stack = Stack()
            undo_stack.undo(x)
        else:
            x.next = self.pointer
            self.pointer = x

    def pop(self):
        if self.is_empty():
            print(f'Stack Underflow')
        else:
            self.pointer = self.pointer.next

    def is_empty(self):
        return self.pointer is None

    def __str__(self):
        string = ''
        current = self.pointer
        while current:
            string += f'{current.data}->'
            current = current.next
        if string:
            print(f'Stack Pointer = {self.pointer.data}')
            return f'[{string[:-2]}]'
        return '[]'

    def undo(self, x):
        self.push(x)
        print(x)

    def redo(self, x):
        self.pop(x)
        print(x)


stack = Stack()

stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)

print(stack)

实施

假设我有一个堆栈

Stack: [5->4->3->2->1]

当我按下 Control+Z 时，undo() 函数调用 pop() 函数并从堆栈中删除最后添加的项目。

5 popped. Stack: [4->3->2->1]

我再次按下 Control+Z，然后：

4 popped. Stack: [3->2->1]

当我按下 Control+Y 时，redo() 函数被调用，之前删除的项目出现在终端上。

4 pushed. Stack: [4->3->2->1]

我再次按 Control+Y，然后

5 pushed. Stack: [5->4->3->2->1]

错误

RecursionError: maximum recursion depth exceeded while calling a Python object

我知道为什么会出现此错误，因为在 push() 中我调用了 undo()，而在 undo() 中我调用了 push() .我应该怎么做才能实现撤消重做功能，我应该创建一个新的 class 并在那个 class 上实现 Undo/Redo 吗？

任何想法/代码都将受到高度赞赏。

Answer 1

这里有一些错误。导致无限递归的主要问题是：

    undo_stack = Stack()
    undo_stack.undo(x)

在这里，您结合了两种不同的方法。您可以在 UndoRedoStack class 中有两个单独的堆栈，并在调用 undo/redo 时来回交换元素，或者你可以有一个双向链接的节点列表，每次你想 undo/redo 时都可以在列表中向上或向下移动。在这里，您似乎两者都在做，并且在此过程中创建了无限数量的 Stack。

相反，您只需添加一行：

else:
    x.next = self.pointer
    self.pointer.prev = x  # You forgot this
    self.pointer = x

那你就不用再叠了。您可以 up/down 链条双向行走。

还有一些其他小错误可能会阻止 class 正常工作。我已经在此处修复了这些问题：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None
        
    def __str__(self):
        return f"Node({self.data})"


class Stack:
    def __init__(self):
        self.pointer = None

    def push(self, x):
        if not isinstance(x, Node):
            x = Node(x)
            
        if self.is_empty():
            self.pointer = x
        else:
            x.next = self.pointer
            self.pointer.prev = x
            self.pointer = x

    def pop(self):
        if self.is_empty():
            print(f'Stack Underflow')
        else:
            self.pointer = self.pointer.next

    def is_empty(self):
        return self.pointer is None

    def __str__(self):
        string = ''
        current = self.pointer
        while current:
            string += f'{current.data}->'
            current = current.next
        if string:
            print(f'Stack Pointer = {self.pointer.data}')
            return f'[{string[:-2]}]'
        return '[]'

    def undo(self):
        x = self.pointer
        self.pop()
        print(x)

    def redo(self):
        x = self.pointer.prev
        if x is None:
            print("nothing to redo")
        else:
            self.push(x)
            print(x)

if __name__ == "__main__":
    stack = Stack()

    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    print("stack is:")
    print(stack)
    print()

    stack.undo()

    print("after undo:")
    print(stack)
    print()

    stack.redo()

    print("after redo:")
    print(stack)

撤消/重做使用堆栈实现

Undo/ Redo Implementation using Stack

python

stack

getch

undo-redo

data-structures

实施

错误