JAVA:
One major application of the Stack data structure is to allow an "undo" and "redo" feature. You will create a program that allows the user to perform mathematical operations and return to previous results.
Each operation the user performs will be applied to whatever the "current value" is. When the program starts, the "current value" should be initialized to 0. In a loop, the user should be continually asked to select from one of four options:
- The first option is to enter a number and a mathematical operator. You only need to include +, *, /, and -. Your program should then perform the desired operation, with "current value" as the left operand and the newly entered number the right operand. For example, if "current value" is 0 and the user enters '5' and '-', calculate 0 - 5. The "current value" then becomes -5.
- The second option is to undo the previously calculated operation. This option should return "current value" to its previous value. Your program should allow the user to undo as many times as they want until they reach the starting point. If they reach the starting point, inform them that they cannot undo any further.
- The third option is to redo the most recent undo. This option should return "current value" to its value before the user selected "undo". Your program should allow the user to redo as many times as they want until there are no more operations to redo.
Note: If at any point the user performs an "undo" and then a new operation, the redo history should be erased.
- The fourth option is to quit the program.
Hint: Your program should use two separate stacks.
The following is some sample output:
Current value is 0 Enter a number, 'u' to undo, 'r' to redo: 5 Enter an operation: + 0 + 5 = 5 Current value is 5 Enter a number, 'u' to undo, 'r' to redo: 10 Enter an operation: - 5 - 10 = -5 Current value is -5 Enter a number, 'u' to undo, 'r' to redo: u Current value is 5 Enter a number, 'u' to undo, 'r' to redo: u Current value is 0 Enter a number, 'u' to undo, 'r' to redo: u No more actions to undo! Current value is 0 Enter a number, 'u' to undo, 'r' to redo: r Current value is 5 Enter a number, 'u' to undo, 'r' to redo: r Current value is -5 Enter a number, 'u' to undo, 'r' to redo: r No more actions to redo! Current value is -5 Enter a number, 'u' to undo, 'r' to redo:
import java.util.EmptyStackException; public interface StackInterface { /** * Adds a new entry to the top of this stack * @param newEntry An object to add to the stack */ void push(T newEntry); /** * Removes and returns this stack's top entry. * @return The object at the top of the stack. * @throws EmptyStackException if the stack is empty */ T pop(); /** * Retrieves this stack's top entry. * @return The object at the top of the stack. * @throws EmptyStackException if the stack is empty */ T peek(); /** * Detects whether this stack is empty * @return True if stack is empty, false otherwise */ boolean isEmpty(); /** * Removes all entries from this stack */ void clear(); }
import java.util.Arrays; import java.util.EmptyStackException; public class ArrayStack implements StackInterface { private T[] entries; private int topIndex; private static final int DEFAULT_CAPACITY = 50; private static final int MAX_CAPACITY = 10000; private static int initialCapacity; public ArrayStack() { this(DEFAULT_CAPACITY); } public ArrayStack(int capacity) { initialCapacity = capacity; clear(); } @Override public void push(T newEntry) { ensureCapacity(); topIndex ++; entries[topIndex] = newEntry; } @Override public T pop() { if (isEmpty()) { throw new EmptyStackException(); } T top = entries[topIndex]; entries[topIndex] = null; topIndex--; return top; } @Override public T peek() { if (isEmpty()) { throw new EmptyStackException(); } else { return entries[topIndex]; } } @Override public boolean isEmpty() { return topIndex == -1; } @Override public void clear() { @SuppressWarnings("unchecked") T[] tempStack = (T[]) new Object[initialCapacity]; entries = tempStack; topIndex = -1; } private void ensureCapacity() { if (topIndex == entries.length - 1) { // array is full. Double its size (if possible) int newLength = 2 * entries.length; checkCapacity(newLength); entries = Arrays.copyOf(entries, newLength); } } private void checkCapacity(int capacity) { if (capacity > MAX_CAPACITY) { throw new IllegalStateException("Capacity too large: " + capacity); } } }