1. Undo using a stack. Use the Stack data structure to implement a simple Undo o
ID: 670461 • Letter: 1
Question
1. Undo using a stack. Use the Stack data structure to implement a simple Undo operation. The user will enter a sequence of positive integers and Undo operations (represented by -1). • As each positive integer is read, it is added to a running total. • As each -1 is read, the previously added number is subtracted from the total. For example, after the follow numbers are read (from left to right), the sum should be 20. 5 2 10 3 If the next integer is -1, the sum should be 17. The most recently added number, 3, is subtracted from the total. A second -1 would result in 7 (10 subtracted from total of 17). The following sequence should yield 8 4 9 3 -1 -1 -1 -1 6 2 Undo for an empty stack should yield zero.
This is what I have so far...
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Stack<Item> implements Iterable<Item> {
private int N; // size of the stack
private Node<Item> first; // top of stack
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
/**
* Initializes an empty stack.
*/
public Stack() {
first = null;
N = 0;
}
/**
* Is this stack empty?
* @return true if this stack is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in the stack.
* @return the number of items in the stack
*/
public int size() {
return N;
}
/**
* Adds the item to this stack.
* @param item the item to add
*/
public void push(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
N++;
}
/**
* Removes and returns the item most recently added to this stack.
* @return the item most recently added
* @throws java.util.NoSuchElementException if this stack is empty
*/
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item; // save item to return
first = first.next; // delete first node
N--;
return item; // return the saved item
}
/**
* Returns (but does not remove) the item most recently added to this stack.
* @return the item most recently added to this stack
* @throws java.util.NoSuchElementException if this stack is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}
/**
* Returns a string representation of this stack.
* @return the sequence of items in the stack in LIFO order, separated by spaces
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}
/**
* Returns an iterator to this stack that iterates through the items in LIFO order.
* @return an iterator to this stack that iterates through the items in LIFO order.
*/
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
/**
* Unit tests the <tt>Stack</tt> data type.
*/
public static void main(String[] args) {
Stack<String> s = new Stack<String>();
while (!StdIn.isEmpty())
{
String item = StdIn.readString();
if (!item.equals("-")) s.push(item);
else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
}
StdOut.println("(" + s.size() + " left on stack)");
}
}
Explanation / Answer
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class Stack<Item> implements Iterable<Item> {
private int N; // size of the stack
private Node<Item> first; // top of stack
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
/**
* Initializes an empty stack.
*/
public Stack() {
first = null;
N = 0;
}
/**
* Is this stack empty?
* @return true if this stack is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in the stack.
* @return the number of items in the stack
*/
public int size() {
return N;
}
/**
* Adds the item to this stack.
* @param item the item to add
*/
public void push(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
// System.out.println("In push->Item : "+item+" -- "+item.toString());
N++;
}
/**
* Removes and returns the item most recently added to this stack.
* @return the item most recently added
* @throws java.util.NoSuchElementException if this stack is empty
*/
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item; // save item to return
first = first.next; // delete first node
N--;
return item; // return the saved item
}
/**
* Returns (but does not remove) the item most recently added to this stack.
* @return the item most recently added to this stack
* @throws java.util.NoSuchElementException if this stack is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}
/**
* Returns a string representation of this stack.
* @return the sequence of items in the stack in LIFO order, separated by spaces
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}
/**
* Returns an iterator to this stack that iterates through the items in LIFO order.
* @return an iterator to this stack that iterates through the items in LIFO order.
*/
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
public int getTotal() {
int sum = 0;
Iterator<Item> iter = this.iterator();
//System.out.print("In total: "+iter);
String current = null;
while(iter != null && iter.hasNext()) {
current = (String) iter.next();
sum += Integer.parseInt(current);
//System.out.print("In total: "+current);
}
System.out.println();
return sum;
}
/**
* Unit tests the <tt>Stack</tt> data type.
*/
public static void main(String[] args) {
Stack<String> s = new Stack<String>();
Scanner scan = new Scanner(System.in);
String item = null;
do
{
item = scan.next();
if(item != null && !item.trim().equals("")) {
try {
//check whether its number or not
int val = Integer.parseInt(item);
if(val != -1 && val < 0)
throw new Exception();
if (!item.equals("-1"))
s.push(item);
else if (!s.isEmpty())
System.out.print(s.pop() + " ");
else
System.out.println(" Stack Empty.");
System.out.println(" Total : "+s.getTotal());
} catch (Exception e) {
System.out.println("Enter positive integer to push or -1 to pop");
}
}
} while(item != null && !item.trim().equals(""));
System.out.println("(" + s.size() + " left on stack)");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.