In this assignment you are to utilize the stack data structure to perform a function that you are familiar with when using Microsoft Word. Many times, you utilize the function Undo and Redo in Word to undo an action that you took, or redo something that you have already undone. If you push undo multiple times, then it will undo the actions that you performed in the reverse order in which you have done them. Similarly it will perform the redo operations by performed a bunch of undo the undos. You can see how a stack data structure is now utilized in this assignment. You must use the stack data structure that is provided in the book. The list-based stack that was provided for you. What you need to do is to start a program by typing an arbitrary sentence with an arbitrary number of words. Once the sentence is entered, you can perform actions on the sentence. Your program should allow for any number of actions to be performed in the order that they appear. The following actions are allowed: add some word delete the previous word added undo the previous action redo a prior undo print the sentence (This is the only action that cannot be undone or redone) o This action should print the sentence after applying any previous actions mentioned before the call to the print. quit to terminate the program These first five actions can actually be listed in any combination, and any one of them can appear multiple times after the first initial sentence is entered (Do not worry about any punctuations, only words and numbers as strings will be entered). Implementation Details: 1. Once the sentence is entered, you should store it in any data structure of your choice. Array, Linked List, its up to you. 2. Upon typing an action, you should perform it on the sentence and then push that action on a stack (only push actions add and delete). 3. Upon doing an undo, you should take the action off the stack, reverse its action on the sentence and push it on a redo stack, so you can redo the undo. 4. If you issue an add or a delete, your redo stack should become empty. Basically, your redo stack can only have items after an undo operation is issued. Once you add or delete, you cant redo, but you can undo as many operations as you have performed so far.

Example Scenario: A sentence with 5 words is entered Please Enter a sentence: Hello welcome to assignment 4 add I add am add going add to add finish add it add quickly print Sentence: Hello welcome to assignment 4 I am going to finish it quickly undo undo undo print Sentence: Hello welcome to assignment 4 I am going to redo redo print Sentence: Hello welcome to assignment 4 I am going to finish it add today add I add think undo undo print Sentence: Hello welcome to assignment 4 I am going to finish it today redo redo print Sentence: Hello welcome to assignment 4 I am going to finish it today I think delete delete print Sentence: Hello welcome to assignment 4 I am going to finish it todayundo undo print Sentence: Hello welcome to assignment 4 I am going to finish it today I think redo print Sentence: Hello welcome to assignment 4 I am going to finish it today I quit