An important application of the Stack data structure is implementing web browser

Undo and Redo operations for a text editor. Write a program in Java to implement

the same. The user will type in a sentence. Store it in a String variable. Now extract

each word from the string from left to right and insert them in a linked list, where

each word will be stored in separate nodes. Now, show a menu to the user to modify a word, delete a word, undo the operations, and redo the operations. Use stack data structure to store the modified$/$ deleted word and its position. The Undo operation will insert the word to its original position, and the Redo operation will repeat the previous modify or delete operation. You can use the Java built$-$in LinkedList and Stack classes.

The sample inputs$/$ outputs are given below:

Enter the sentence: The quick brown fox jumps over the lazy dog

Press $1$ to delete a word

Press $2$ to change a word

Press $3$ to undo an operation

Press $4$ to redo an operation

Press $5$ to exit

Enter your choice: $3$

Sorry, can$$t undo any previous operation$($s$)$

Enter your choice: $4$

Sorry, can$$t redo any previous operation$($s$)$

Enter your choice: $2$

Enter the word to modify: brown

Enter the new word: red

The word is changed. The modified sentence is:

The quick red fox jumps over the lazy dog

Enter your choice: $1$

Enter the word to delete: over

The word is removed. The modified sentence is:

The quick red fox jumps the lazy dog

Enter your choice: $3$

Undo operation is done. The sentence: The quick red fox jumps over the lazy dog

Enter your choice: $3$

Undo operation is done. The sentence: The quick brown fox jumps over the lazy dog

Enter your choice: $4$

Redo operation is done. The sentence: The quick red fox jumps over the lazy dog

Enter your choice: $5$

Thank you!

$[$Hint: Use two stacks, one for undo operation and another for redo operation. Both

stacks will contain the changed$/$ deleted word, its position, and the operation $($modify or delete$).$ In case of a modify or delete operation, push the original word and its position into the undo stack. In case of an undo operation, pop the topmost word and its position, insert the word in the proper position of the sentence and finally, push them in the redo stack. In case of a redo operation, pop the topmost word, modify$/$ delete the word from the sentence as per the operation, and push the information into the undo stack. If there are multiple occurrences of the same word, change or delete the first occurrence.$]$

The linked list representation of the sentence $$The quick brown fox$$:

The sample undo stack:

In the above sample undo stack, each cell contains three information, the word, its

position in the sentence, and the operation $($d $->$ delete, m $->$ modify$).$ Create the redo

stack similarly.