Question

For this assignment you will be writing a program that evaluates some PostScript® commands. Specifically, you will be using a special version of a linked-list, called a Stack. Stacks are linear structures that are used in many applications. In fact, Java's runtime environment (JRE) uses a stack to evaluate Java's byte-code. You can learn more about Stacks from this URL:

Tutorialspoint - Stack (Links to an external site.)

The stack description above uses an array implementation for examples. You will be not be using arrays, you will be using linked-lists. PostScript is known as a "page description" programming language, because it is commonly used to specify how a page should be printed. PostScript is a sequence of commands in the PostScript language. You can learn more about PostScript from this URL:

PostScript (Wikipedia) (Links to an external site.)

PostScript commands and data are processed by using a stack. You'll see that stacks have a distinctive characteristic that all of its operations are done at the beginning or "top" of the structure. Your job will be to implement the four basic stack methods which are  push(), pop(), peek() and isEmpty() along with other specific methods to handle PostScript commands.

PostScript data are pushed onto the stack. Below are the PostScript commands you must implement along with their descriptions and examples, where "->" signifies the top of he stack (blue designates input, red designates output):

• pop: This command is the same as the definition of the pop() method for a stack.

  35 -100 22 pop
  -> -100 35
  

• dup: replicates the top element of the stack and pushes it on the stack.

  13 12 dup
  -> 12 12 13
  

• exch: exchanges the top two items.

  13 -50 exch
  -> 13 -50 
  

• clear: empties out the stack.

  1 -50 22 100 99 6 clear
  -> <empty>
  

• n index: pops the n, counts down n items into the stack and then pushes a copy of the nth element to the stack. Clear the stack if there are not enough elements.

  34 12 92 2 index
  -> 12 92 12 34
  

• n copy: pops the n, and then pushes a copy of the top n elements onto the stack. Clear the stack if there are not enough elements.

  12 6 2 copy
  -> 12 6 6 12
  

• count: the number of items on the stack and push that value onto the stack.

  10 20 30 40 50 count
  -> 5 50 40 30 20 10
  

Programming Notes:

1. You can add or delete any methods. You can add or delete any code.
2. You must use a singly-linked list but you can choose your own list implementation such-as with or without sentinels, with head and/or tail points, etc.
3. Do not assume any maximum length for any input string.
4. You need not test for the null or empty string ("") cases.

Programming Rules:

1. You are not allowed to add any arrays or ArrayLists or any Java built-in (ADTs), such as Lists, Sets, Maps, Stacks, Queues, Deques, Trees, Graphs, Heaps, etc. Or add any class that inherits any of those ADTs.
2. For your node and list class you can use the code that was used in the book, video and lecture notes related to the node and lists class examples.
3. You are not allowed to use Java Generics.
4. If hard-coding detected in any part of your solution your score will be zero for the whole assignment.

Submission Rules:

1. Submit only one Homework6.java file for all test cases. The starter file name is Homework6a.java so you will need rename the file before you begin submitting your solution.

2. Anything submitted to Mimir is considered to be officially submitted to me and is considered to be 100% your work. Even if it is not your last planned submission.

3. Any extra testing code that you wrote and used to do your own testing must be deleted from the file that gets used in the final grading. Commenting out code is not sufficient and not considered deleted. English comments written to explain your code are perfectly fine.

STARTER CODE:

import java.util.Scanner;  // Import the Scanner class

public class Homework6 {

  

   public static void main(String[] args) {

     PSStack a = makeStack();

     a.displayStack();

   }

   

   public static PSStack makeStack() {

     PSStack temp = new PSStack();     

     Scanner input = new Scanner(System.in);

     String s = input.nextLine();

     String[] array = s.split(" ");

     for (String command : array){

       temp.evaluate(command);

     }

     return temp;

   }  

}

class StackNode {

  

  public String    data;

  public StackNode next;

  public StackNode (String s) {

    data = s;

    next = null;

  }

}

class Stack {

  

  public StackNode top;

  public int size;

  

  public Stack() {

    top  = null;

  }

  

  public void push(String command) {

    StackNode temp = null;

    if (top == null) {

      top = new StackNode(command);

    }

    else {

      temp = top;

      top = new StackNode(command);

      top.next = temp;

    }  

  }

  

  public StackNode pop() {

    if (isEmpty()) {

      System.out.println("Not enough items on the stack to perform this operation.");

      return null;

    }

    else {

      StackNode temp = top;

      top = top.next;

      return temp;

    }

  }

  

  public String peek() {

      return null;

  }  

  

  public boolean isEmpty() {

      return true;

  }  

}

  

class PSStack extends Stack {

    

  public void displayStack() {

    System.out.print("-> ");

    System.out.print("<empty>");

    System.out.println("Not enough items on the stack to perform this operation."); //copy and paste this anywhere you need

    // put your solution here

   }

    public void exch() {

      // put your solution here

    }

    

    public void dup() {

    // put your solution here

    }

    

    public void clear() {

    // put your solution here

    }

    

    public void count() {

    // put your solution here

    }

    

    public void index() {

    // put your solution here

   }

    

    public void copy() {

    // put your solution here

    }

    

    public void evaluate(String command) {

    // put your solution here  

    }           

}     

Answer 1

Homework6.java

import java.util.Scanner;

public class Homework6 {

public static void main(String[] args)
{
   PSStack a = makeStack();
    a.displayStack();
}

public static PSStack makeStack() {

PSStack temp = new PSStack();   
Scanner input = new Scanner(System.in);
String s = input.nextLine();
String[] array = s.split(" ");
for (String command : array)
{
temp.evaluate(command);
}
input.close();
return temp;
}
}

class StackNode {

   public String data;
   public StackNode next;
   public StackNode (String s) {
   data = s;
   next = null;
   }
   }

   class Stack {
   public StackNode top;
   public int size;
   public Stack() {
   top = null;
   }

   public void push(String command) {
   StackNode temp = null;
   if (top == null) {
   top = new StackNode(command);
   }
   else {
   temp = top;
   top = new StackNode(command);
   top.next = temp;
   }
   size++;
   }

   public StackNode pop()
   {
   if (isEmpty())
   {
   System.out.println("Not enough items on the stack to perform this operation.");
   return null;
   }
   else
   {
   StackNode temp = top;
   top = top.next;
   size--;
   return temp;
   }
   }
  
   public String peek() {
       if (isEmpty())
       {
       System.out.println("Not enough items on the stack to perform this operation.");
       return null;
       }
       else
       {
       StackNode temp = top;
       return temp.data;
       }
   }

   public boolean isEmpty()
   {
       if(size == 0)
           return true;
       return false;
   }
   }

   class PSStack extends Stack {

   public void displayStack()
   {
   System.out.print("-> ");
     
   if(size == 0)
   {
   System.out.print("<empty>");
       return;
   }
  
   StackNode temp = top;
   while(temp != null)
   {
   System.out.print(temp.data + " ");
       temp = temp.next;
   }

   }
   public void exch()
   {
       String top_element = pop().data;
       String second_element = pop().data;
       push(top_element);
       push(second_element);
   }

   public void dup()
   {
       String top_element = peek();
       push(top_element);
   }

   public void clear()
   {
       while(size > 0)
       {
           pop();
       }
   }  

   public void count()
   {
       //count: the number of items on the stack and push that value onto the stack.
       push(Integer.toString(size));
   }  

   public void index()
   {
       // n index: pops the n, counts down n items into the stack and then pushes a copy of the nth element to the stack.
       //Clear the stack if there are not enough elements.
       int n = Integer.parseInt(pop().data);
       int i=0;
      
       if(size < n)
       {
           clear();
           return;
       }
      
       StackNode element = top;
       for(i = 0; i< n-1; i++)
       {
           element = element.next;
       }
       push(element.data);
   }

   public void copy()
   {
       //n copy: pops the n, and then pushes a copy of the top n elements onto the stack.
       //Clear the stack if there are not enough elements.
       int n = Integer.parseInt(pop().data);
       int i=0;
      
       if(size < n)
       {
           clear();
           return;
       }
      
       //store n elements into a temporary stack temp
       PSStack temp = new PSStack();
      
       StackNode element = top;
       for(i = 0; i< n-1; i++)
       {
           temp.push(element.data);
           element = element.next;
       }
       temp.push(element.data);
      
      
       // now we will push all elements stored into original stack
       if(temp.isEmpty() == true)
       {
           return;
       }
       StackNode e = temp.pop();
       while(!temp.isEmpty())
       {
           push (e.data);
           e = temp.pop();
       }   
       push(e.data);
   }

   public void evaluate(String command)
   {
       if(command.equalsIgnoreCase("pop"))
       {
           pop();
       }
       else if(command.equalsIgnoreCase("dup"))
       {
           dup();
       }
       else if(command.equalsIgnoreCase("exch"))
       {
           exch();
       }
       else if(command.equalsIgnoreCase("index"))
       {
           index();
       }
       else if(command.equalsIgnoreCase("copy"))
       {
           copy();
       }
       else if(command.equalsIgnoreCase("count"))
       {
           count();
       }
       else if(command.equalsIgnoreCase("clear"))
       {
           clear();
       }
       else if(command.matches("-?(0|[1-9]\\d*)"))
       {
           push(command);
       }
       else
       {
           System.out.println("Invalid Input");
       }
  
   }   
   }   

Sample I/O and output