Undo/ Redo Implementation using Stack

Question

I want to implement Undo-Redo functionality using stacks. When the user presses Ctrl+Z the last node will be removed from the screen. When the user press again Ctrl+Z then the "last.last" node will be removed from the screen and if he presses Ctrl+Y then the last removed node will display again on the screen.

Below is my code:

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)

Implementation

Suppose I have a stack

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

When I press Control+Z, the undo() function calls the pop() function and removes the last added item from the stack.

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

again I press Control+Z, then:

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

When I press Control+Y the redo() function is called and the previously removed items appear on the terminal.

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

again I press Control+Y, then

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

Error

RecursionError: maximum recursion depth exceeded while calling a Python object

I know why this error occurs because inside the push() I made a call to the undo(), and inside the undo() I made a call to the push(). What should I do to implement undo-redo functionality, should I make a new class and implement Undo/Redo on that class?

Any ideas/ code will be highly appreciatable.

Answer 1

There are a few errors in this. The main issue causing the infinite recursion is this:

    undo_stack = Stack()
    undo_stack.undo(x)

Here, you are combining two different approaches. You could either have two separate stacks in your UndoRedoStack class and swap elements back and forth when undo/redo is called, or you could have a single doubly-linked list of nodes and step up or down the list every time you want to undo/redo. Here, you seem to be doing both, and you are creating an infinite number of Stacks in the process.

Instead, all you need to do is add one line:

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

Then, you don't need to make any other stacks. You can just walk up/down the chain in both directions.

There were also a number of other small mistakes that would have prevented the class from working as intended. I've fixed those up here:

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)