Implement Undo and Redo features of a Text Editor

Given an array of strings Q[], consisting of queries of the following types:

• “WRITE X”: Write a character X into the document.
• “UNDO”: Erases the last change made to the document.
• “REDO”: Restores the most recent UNDO operation performed on the document.
• “READ”: Reads and prints the contents of the documents.

Examples:

Input: Q =
Output: AB ABC
Explanation:
Perform “WRITE A” on the document. Therefore, the document contains only “A”.
Perform “WRITE B” on the document. Therefore, the document contains “AB”.
Perform “WRITE C” on the document. Therefore, the document contains “ABC”.
Perform “UNDO” on the document. Therefore, the document contains “AB”.
Print the contents of the document, i.e. “AB”
Perform “REDO” on the document. Therefore, the document contains “ABC”.
Print the contents of the document, i.e. “ABC”

Input: Q =
Output:xz xzy

Approach: The problem can be solved using Stack. Follow the steps below to solve the problem:

• Initialize two stacks, say Undo and Redo.
• Traverse the array of strings, Q, and perform the following operations:
• If “WRITE” string is encountered, push the character to Undo stack
• If “UNDO” string is encountered, pop the top element from Undo stack and push it to Redo stack.
• If “REDO” string is encountered, pop the top element of Redo stack and push it into the Undo stack.
• If “READ” string is encountered, print all the elements of the Undo stack in reverse order.

Below is the implementation of the above approach: