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:

Once the sentence is entered, you should store it in any data structure of your choice. Array, Linked List, its up to you.

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).

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.

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 today undo

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

ListStack

public class ListStack { /** * Construct the stack. */ public ListStack( ) { topOfStack = null; }

/** * Test if the stack is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return topOfStack == null; }

/** * Make the stack logically empty. */ public void makeEmpty( ) { topOfStack = null; }

/** * Insert a new item into the stack. * @param x the item to insert. */ public void push( AnyType x ) { topOfStack = new ListNode( x, topOfStack ); }

/** * Remove the most recently inserted item from the stack. * @throws UnderflowException if the stack is empty. */ public void pop( ) { if( isEmpty( ) ) throw new UnderflowException( "ListStack pop" ); topOfStack = topOfStack.next; }

/** * Get the most recently inserted item in the stack. * Does not alter the stack. * @return the most recently inserted item in the stack. * @throws UnderflowException if the stack is empty. */ public AnyType top( ) { if( isEmpty( ) ) throw new UnderflowException( "ListStack top" ); return topOfStack.element; }

/** * Return and remove the most recently inserted item * from the stack. * @return the most recently inserted item in the stack. * @throws UnderflowException if the stack is empty. */ public AnyType topAndPop( ) { if( isEmpty( ) ) throw new UnderflowException( "ListStack topAndPop" );

AnyType topItem = topOfStack.element; topOfStack = topOfStack.next; return topItem; }

private ListNode topOfStack; }

ListNode

public class ListNode { // Basic node stored in a linked list // Note that this class is not accessible outside // of package weiss.nonstandard

class ListNode { // Constructors public ListNode( AnyType theElement ) { this( theElement, null ); }

public ListNode( AnyType theElement, ListNode n ) { element = theElement; next = n; }

public AnyType element; public ListNode next; }

}

ListQueue

public class ListQueue { /** * Construct the queue. */ public ListQueue( ) { front = back = null; }

/** * Test if the queue is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return front == null; }

/** * Insert a new item into the queue. * @param x the item to insert. */ public void enqueue( AnyType x ) { if( isEmpty( ) ) // Make queue of one element back = front = new ListNode( x ); else // Regular case back = back.next = new ListNode( x ); }

/** * Return and remove the least recently inserted item * from the queue. * @return the least recently inserted item in the queue. * @throws UnderflowException if the queue is empty. */ public AnyType dequeue( ) { if( isEmpty( ) ) throw new UnderflowException( "ListQueue dequeue" );

AnyType returnValue = front.element; front = front.next; return returnValue; }

/** * Get the least recently inserted item in the queue. * Does not alter the queue. * @return the least recently inserted item in the queue. * @throws UnderflowException if the queue is empty. */ public AnyType getFront( ) { if( isEmpty( ) ) throw new UnderflowException( "ListQueue getFront" ); return front.element; }

/** * Make the queue logically empty. */ public void makeEmpty( ) { front = null; back = null; }

private ListNode front; private ListNode back; }