使用栈实现撤销/重做

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)

<标题>

实现假设有一个堆栈

堆栈:[5→4→3→2→1]

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

5了。栈:[4→3→2→1]

再次按下Control+Z，然后:

4了。栈:[3→2→1)

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

4把。栈:[4→3→2→1]

再次按Control+Y，然后按

5推。栈:[5→4→3→2→1]

<标题>错误

RecursionError: maximum recursion depth exceeded while calling a Python object

我知道为什么会发生这个错误，因为在push()中我调用了undo()，在undo()中我调用了push()。我应该做些什么来实现撤销/重做功能，我应该做一个新的类和实现撤销/重做的类吗?

任何想法/代码都将非常感谢。

Answer 1

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

undo_stack = Stack()
undo_stack.undo(x)

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

相反，你所需要做的只是添加一行:

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

然后，您不需要创建任何其他堆栈。你可以在两个方向上下走。

还有其他一些小错误可能会阻止类按预期工作。我把它们固定在这里:

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)