Question: First step is to use to read in a program for the computer to execute from a file into a queue of nodes (the input
First step is to use to read in a program for the computer to execute from a file into a queue of nodes (the input queue in the above examples). You have been given a node class (Node) and do not need to edit this is any way. However, if you open Computer.java you will see a method called fileToNodeQueue()which needs to be completed. Using the Java Scanner class, youll need to turn an input text file into a Node queue of symbols the computer can process (symbols are space separated, you may assume only one space between each symbol if that is helpful).
//FILL IN METHODS AS INSTRUCTED IN COMMENTS
PROGRAM STACK CLASS
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
class ProgramStack
// You'll want some instance variables here
protected Object[] elementData;
private int modCount;
private int elementCount;
private int lastRet;
private int expectedModCount;
private int cursor;
private int initialCapacity=10;
public ProgramStack() {
//setup what you need
this.elementData = new Object[initialCapacity];
}
public void push(T item) {
//push an item onto the stack
//you may assume the item is not null
//O(1)
addElement(item);
}
public T pop() {
//pop an item off the stack
//if there are no items on the stack, return null
//O(1)
//replace this dummy return statement
//return null;
T obj;
int len = size();
obj = peek();
if(len == 0){
return null;
}
removeElementAt(len - 1);
return obj;
}
public T peek() {
//return the top of the stack (but don't remove it)
//if there are no items on the stack, return null
//O(1)
//replace this dummy return statement
//return null;
int len = size();
if (len == 0)
return null;
return elementAt(len - 1);
}
public String toString() {
//Create a string of the stack where each item
//is separated by a space. The top of the stack
//should be shown to the right and the bottom of
//the stack on the left.
//Hint: Reuse the provided code from another class
//instead of writing this yourself!
//O(n)
//replace this dummy return statement
//return null;
if (elementData == null)
return "null";
int iMax = elementData.length - 1;
if (iMax == -1)
return "";
StringBuilder b = new StringBuilder();
for (int i = 0; ; i++) {
if(elementData[i]!=null)
b.append(String.valueOf(elementData[i]));
if (i == iMax)
return b.toString().trim();
b.append(" ");
}
}
public void clear() {
//remove everything from the stack
//O(1)
modCount++;
// Let gc do its work
for (int i = 0; i < elementCount; i++)
elementData[i] = null;
elementCount = 0;
}
public int size() {
//return the number of items on the stack
//O(1)
//replace this dummy return statement
return elementCount;
}
public boolean isEmpty() {
//return whether or not the stack is empty
//O(1)
//replace this dummy return statement
return size() == 0;
}
@SuppressWarnings("unchecked")
public Object[] toArray() {
//Return an array representation of the stack.
//The top of the stack should be element 0
//in the array.
//O(n)
//replace this dummy return statement
//return null;
return Arrays.copyOf(elementData, elementCount);
}
public Iterator
//Return an iterator that traverses from
//the top of the stack to the bottom of
//the stack.
//The iterator's hasNext() and next() methods
//must both be O(1)
//next() should throw a NullPointerException
//if you try to use next when there are no
//more items
//replace this dummy return statement
//return null;
return new Itr();
}
public static void main(String[] args) {
ProgramStack
s1.push("a");
s1.push("b");
ProgramStack
s2.push(1);
s2.push(2);
s2.push(3);
if(s1.toString().equals("a b") && s1.toArray()[0].equals("b") && s1.toArray()[1].equals("a") && s1.toArray().length == 2) {
System.out.println("Yay 1");
}
if(s1.peek().equals("b") && s2.peek().equals(3) && s1.size() == 2 && s2.size() == 3) {
System.out.println("Yay 2");
}
if(s1.pop().equals("b") && s2.pop().equals(3) && s1.size() == 1 && s2.size() == 2) {
System.out.println("Yay 3");
}
if(s1.toString().equals("a") && s1.peek().equals("a") && s2.peek().equals(2) && s1.pop().equals("a") && s2.pop().equals(2) && s1.size() == 0 && s2.size() == 1) {
System.out.println("Yay 4");
}
if(s1.toString().equals("") && s1.peek() == null && s2.peek().equals(1) && s1.pop() == null && s2.pop().equals(1) && s1.size() == 0 && s2.size() == 0) {
System.out.println("Yay 5");
}
s2.push(10);
s2.push(20);
s2.push(30);
if(s1.isEmpty() && s1.toArray().length == 0 && !s2.isEmpty()) {
s2.clear();
if(s2.isEmpty()) {
System.out.println("Yay 6");
}
}
ProgramStack
s3.push(3);
s3.push(2);
s3.push(1);
int i = 1;
for(Integer item : s3) {
if(i == item) System.out.println("Yay " + (6+i));
else
System.out.println(item);
i++;
}
}
public synchronized void addElement(T obj) {
modCount++;
elementData[elementCount++] = obj;
}
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
public synchronized T elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
@SuppressWarnings("unchecked")
T elementData(int index) {
return (T) elementData[index];
}
private class Itr implements Iterator
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
// Racy but within spec, since modifications are checked
// within or after synchronization in next/previous
return cursor != elementCount;
}
public T next() {
synchronized (ProgramStack.this) {
checkForComodification();
int i = cursor;
if (i >= elementCount)
throw new NoSuchElementException();
cursor = i + 1;
return elementData(lastRet = i);
}
}
public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
synchronized (ProgramStack.this) {
checkForComodification();
ProgramStack.this.remove(lastRet);
expectedModCount = modCount;
}
cursor = lastRet;
lastRet = -1;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
public void remove(int lastRet2) {
if (lastRet == -1)
throw new IllegalStateException();
synchronized (ProgramStack.this) {
checkForComodification();
ProgramStack.this.remove(lastRet);
expectedModCount = modCount;
}
cursor = lastRet;
lastRet = -1;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
TABLE CLASS
class SymbolTable
private TableEntry
@SuppressWarnings("unchecked")
public SymbolTable(int size) {
//Create a hash table where the initial storage
//is size and string keys can be mapped to T values.
//You may assume size is >= 2
}
public int getCapacity() {
//return how big the storage is
//O(1)
}
public int size() {
//return the number of elements in the table
//O(1)
}
public void put(String k, T v) {
//Place value v at the location of key k.
//Use linear probing if that location is in use.
//You may assume both k and v will not be null.
//Hint: Make a TableEntry to store in storage
//and use the absolute value of k.hashCode() for
//the probe start.
//If the key already exists in the table
//replace the current value with v.
//If the key isn't in the table and the table
//is >= 80% full, expand the table to twice
//the size and rehash
//Worst case: O(n), Average case: O(1)
}
public T remove(String k) {
//Remove the given key (and associated value)
//from the table. Return the value removed.
//If the value is not in the table, return null.
//Hint 1: Remember to leave a tombstone!
//Hint 2: Does it matter what a tombstone is?
// Yes and no... You need to be able to tell
// the difference between an empty spot and
// a tombstone and you also need to be able
// to tell the difference between a "real"
// element and a tombstone.
//Worst case: O(n), Average case: O(1)
}
public T get(String k) {
//Given a key, return the value from the table.
//If the value is not in the table, return null.
//Worst case: O(n), Average case: O(1)
}
public boolean isTombstone(int index) {
//this is a helper method needed for printing
//return whether or not there is a tombstone at the
//given index
//O(1)
}
@SuppressWarnings("unchecked")
public boolean rehash(int size) {
//Increase or decrease the size of the storage,
//rehashing all values.
//If the new size won't fit all the elements,
//return false and do not rehash. Return true
//if you were able to rehash.
}
public static void main(String[] args) {
//main method for testing, edit as much as you want
SymbolTable
SymbolTable
if(st1.getCapacity() == 10 && st2.getCapacity() == 5 && st1.size() == 0 && st2.size() == 0) {
System.out.println("Yay 1");
}
st1.put("a","apple");
st1.put("b","banana");
st1.put("banana","b");
st1.put("b","butter");
if(st1.toString().equals("a:apple b:butter banana:b") && st1.toStringDebug().equals("[0]: null [1]: null [2]: null [3]: null [4]: null [5]: null [6]: null [7]: a:apple [8]: b:butter [9]: banana:b")) {
System.out.println("Yay 2");
}
if(st1.getCapacity() == 10 && st1.size() == 3 && st1.get("a").equals("apple") && st1.get("b").equals("butter") && st1.get("banana").equals("b")) {
System.out.println("Yay 3");
}
st2.put("a",1);
st2.put("b",2);
st2.put("e",3);
st2.put("y",4);
if(st2.toString().equals("e:3 y:4 a:1 b:2") && st2.toStringDebug().equals("[0]: null [1]: e:3 [2]: y:4 [3]: null [4]: null [5]: null [6]: null [7]: a:1 [8]: b:2 [9]: null")) {
System.out.println("Yay 4");
}
if(st2.getCapacity() == 10 && st2.size() == 4 && st2.get("a").equals(1) && st2.get("b").equals(2) && st2.get("e").equals(3) && st2.get("y").equals(4)) {
System.out.println("Yay 5");
}
if(st2.remove("e").equals(3) && st2.getCapacity() == 10 && st2.size() == 3 && st2.get("e") == null && st2.get("y").equals(4)) {
System.out.println("Yay 6");
}
if(st2.toString().equals("y:4 a:1 b:2") && st2.toStringDebug().equals("[0]: null [1]: tombstone [2]: y:4 [3]: null [4]: null [5]: null [6]: null [7]: a:1 [8]: b:2 [9]: null")) {
System.out.println("Yay 7");
}
if(st2.rehash(2) == false && st2.size() == 3 && st2.getCapacity() == 10) {
System.out.println("Yay 8");
}
if(st2.rehash(4) == true && st2.size() == 3 && st2.getCapacity() == 4) {
System.out.println("Yay 9");
}
if(st2.toString().equals("y:4 a:1 b:2") && st2.toStringDebug().equals("[0]: null [1]: y:4 [2]: a:1 [3]: b:2")) {
System.out.println("Yay 10");
}
SymbolTable
st3.put("a","a");
st3.remove("a");
if(st3.toString().equals("") && st3.toStringDebug().equals("[0]: null [1]: tombstone")) {
st3.put("a","a");
if(st3.toString().equals("a:a") && st3.toStringDebug().equals("[0]: null [1]: a:a") && st3.toStringDebug().equals("[0]: null [1]: a:a")) {
System.out.println("Yay 11");
}
}
}
//--------------Provided methods below this line--------------
//Add JavaDocs, but do not change the methods.
public String toString() {
//THIS METHOD IS PROVIDED, DO NOT CHANGE IT
StringBuilder s = new StringBuilder();
for(int i = 0; i < storage.length; i++) {
if(storage[i] != null && !isTombstone(i)) {
s.append(storage[i] + " ");
}
}
return s.toString().trim();
}
public String toStringDebug() {
//THIS METHOD IS PROVIDED, DO NOT CHANGE IT
StringBuilder s = new StringBuilder();
for(int i = 0; i < storage.length; i++) {
if(!isTombstone(i)) {
s.append("[" + i + "]: " + storage[i] + " ");
}
else {
s.append("[" + i + "]: tombstone ");
}
}
return s.toString().trim();
}
}
NODE CLASS
//Do not edit this class, just add JavaDocs
//You may edit the main method for testing things if you want
//but do not change the actual class structure.
class Node
private T value;
private Node
private Node
public Node(T value) {
this.value = value;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public Node
return this.next;
}
public void setNext(Node
this.next = next;
}
public Node
return this.prev;
}
public void setPrev(Node
this.prev = prev;
}
public static String listToString(Node head) {
StringBuilder ret = new StringBuilder();
Node current = head;
while(current != null) {
ret.append(current.value);
ret.append(" ");
current = current.getNext();
}
return ret.toString().trim();
}
public static String listToStringBackward(Node head) {
Node current = head;
while(current.getNext() != null) {
current = current.getNext();
}
StringBuilder ret = new StringBuilder();
while(current != null) {
ret.append(current.value);
ret.append(" ");
current = current.getPrev();
}
return ret.toString().trim();
}
public static void main(String[] args) {
//main method for testing, edit as much as you want
//make nodes
Node
Node
Node
//connect forward references
n1.setNext(n2);
n2.setNext(n3);
//connect backward references
n3.setPrev(n2);
n2.setPrev(n1);
//print forward and backward
System.out.println(Node.listToString(n1));
System.out.println(Node.listToStringBackward(n1));
}
}
COMPUTER CLASS
//These are all the imports you are allowed, don't add any more! import java.util.Scanner; import java.io.File; import java.io.IOException; class Computer { public static Node fileToNodeQueue(String filename) throws IOException { //given a file name, open that file in a scanner and create a queue of nodes //the head of the queue of nodes should be the start of the queue //the values in the nodes should be the strings read in each time you call //next() on the scanner return null; } public Node process(Node input, int numSymbols) { //Given an input queue of symbols process the number of symbols //specified (numSymbols) and update the progStack and symbols //variables appropriately to reflect the state of the "computer" //(see below the "do not edit" line for these variables). //Return the remaining queue items. //For example, if input is the head of a linked list 3 -> 2 -> + //and numSymbols=2, you would push 3 and push 2, then return the linked //list with just the + node remaining. return null; } public static void testMain() { //edit this as much as you want, if you use main without any arguments, //this is the method that will be run instead of the program System.out.println("You need to put test code in testMain() to run Computer with no parameters."); } //--------------------DON'T EDIT BELOW THIS LINE-------------------- //----------------------EXCEPT TO ADD JAVADOCS---------------------- //don't edit these... public static final String[] INT_OPS = {"+","-","*","/"}; public static final String[] ASSIGN_OPS = {"=","+=","-=","*=","/="}; //or these... public ProgramStackprogStack = new ProgramStack<>(); public SymbolTable symbols = new SymbolTable<>(5); public static void main(String[] args) { //this is not a testing main method, so don't edit this //edit testMain() instead! if(args.length == 0) { testMain(); return; } if(args.length != 2 || !(args[1].equals("false") || args[1].equals("true"))) { System.out.println("Usage: java Computer [filename] [true|false]"); System.exit(0); } try { (new Computer()).runProgram(args[0], args[1].equals("true")); } catch(IOException e) { System.out.println(e.toString()); e.printStackTrace(); } } //provided, don't change this public void runProgram(String filename, boolean debug) throws IOException { Node input = fileToNodeQueue(filename); System.out.println(" Program: " + Node.listToString(input)); if(!debug) { while(input != null) { input = process(input, 10); } } else { Scanner s = new Scanner(System.in); for(int i = 1; input != null; i++) { System.out.println(" ######### Step " + i + " ############### "); System.out.println("----------Step Output----------"); input = process(input, 1); System.out.println("----------Symbol Table---------"); System.out.println(symbols); System.out.println("----------Program Stack--------"); System.out.println(progStack); if(input != null) { System.out.println("----------Program Remaining----"); System.out.println(Node.listToString(input)); } System.out.println(" Press Enter to Continue"); s.nextLine(); } } } }
TABLE ENTRY CLASS
//Do not edit this class, just add JavaDocs
class TableEntry
private K key;
private V value;
public TableEntry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public String toString() {
return key.toString()+":"+value.toString();
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help