Given the three classes (CallStack, LookUpBST, and Node) fill in what is needed in the SimpleCompiler Class, and also the rest of what's needed in the LookUpBST class

class LookUpBSTextends Comparable, V> {

//Root of tree

public Node root;

public int size;

public int size() { return size; }

public static class Node {

K key; // sorted by key

V val; // associated data

Node left, right; // left and right subtrees

public Node(K key, V val) {

this.key = key;

this.val = val;

}

public Node(K key, V val, Node l, Node r) {

this.key = key;

this.val = val;

this.left = l;

this.right = r;

}

}

// You can NOT add any instance/static variables in this class.

// You can add methods if needed but they must be PRIVATE.

//-------------------------------------------------------------

public boolean contains(K key) {

// Return true if key is in tree;

// return false if key is not in tree or if key is null.

// O(H): H as the tree height

return false;

}

public V get(K key) {

// Return the value associated with the given key if the key is in tree

// Return null if the key is not in tree

// throw IllegalArgumentException if key is null

// O(H): H as the tree height

return null;

}

public boolean put(K key, V val) {

// Insert key, val into tree.

// If key is in tree, replace already existing value for this key with the given parameter val

// Return false if key, val cannot be added

// (null keys).

// Return true for a successful insertion.

// O(H): H as the tree height

return false;

}

public static K findBiggestKey(Node t) {

// Return the biggest key in the tree rooted at t.

// Return null if tree is null.

// O(H): H as the tree height

return null;

}

public int height() {

// Return the height of the tree.

// Return -1 for null trees.

// O(N): N is the tree size

return 0;

}

public int numLeaves() {

// Return the number of leaf nodes in the tree.

// Return zero for null trees.

// O(N): N is the tree size

return 0;

}

public String toString() {

// Returns a string representation of the tree

// Change the function call below to

// toStringInOrder: to see (IN-ORDER) string representation of LookUpBST while in debug mode

// toStringLevelOrder: to see (LEVEL-ORDER) string representation of LookUpBST in level-order traversal while in debug mode

return toStringInOrder(this.root);

}

private String toStringInOrder(Node t){

// Follow IN-ORDER traversal to include data of all nodes.

// Example 1: a single-node tree with the root data as "a:112":

// toString() should return a:112

//

// Example 2: a tree with four nodes:

// d:310

// / \

// a:112 p:367

// /

// f:330

// toStringInOrder() should return a:112 d:310 f: 330 p:367

if (t==null)

return "";

StringBuilder sb = new StringBuilder();

sb.append(toStringInOrder(t.left));

sb.append(t.key);

sb.append(":");

sb.append(t.val);

sb.append(" ");

sb.append(toStringInOrder(t.right));

return sb.toString();

}

private String toStringLevelOrder(Node t) {

// Follow LEVEL-ORDER traversal to include data of all nodes.

// Example: a tree with four nodes:

// d:310

// / \

// a:112 p:367

// /

// f:330

// toStringLevel() should return

// d:310

// a:112 p:367

// null null f:330 null

StringBuilder sb = new StringBuilder();

int capacity = (int)Math.pow(2,size()+1)-1;

Node,?>[] list = new Node,?>[capacity];

list[0] = root;

int count = 0;

int level = 0;

for(int i = 0; i

if(i == Math.pow(2,level+1)-1) {

if(count == size) break;

level++;

sb.append(" ");

}

if(list[i] == null) {

sb.append("null ");

}

else {

count++;

sb.append(list[i].key);

sb.append(":");

sb.append(list[i].val);

sb.append(" ");

if((i*2)+1

list[(i*2)+1] = list[i].left;

list[(i*2)+2] = list[i].right;

}

}

}

return sb.toString();

}

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

//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 SimpleCompiler {

public static Node fileToQueue(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

/ext() on the scanner

return null;

}

public Node compile(Node input, int numSymbols) {

//Given an input queue of symbols, process the number of symbols

//specified (numSymbols) and update the callStack and symbols

//variables appropriately to reflect the state of the "SimpleCompiler"

//(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 testThisCode() {

//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 testThisCode() to run SimpleCompiler with no parameters.");

}

//--------------------DON'T EDIT BELOW THIS LINE--------------------

//----------------------EXCEPT TO ADD JAVADOCS----------------------

public static final String[] INT_OPS = {"+","-","*","/"};

public static final String[] ASSIGN_OPS = {"=","+=","-=","*=","/="};

//or these...

public CallStack

public LookUpBST symbols = new LookUpBST();

public static void main(String[] args) {

//this is not a testing main method, so don't edit this

//edit testThisCode() instead!

if(args.length == 0) {

testThisCode(); //THIS IS WHAT SHOULD BE EDITTED

return;

}

if(args.length != 2 || !(args[1].equals("false") || args[1].equals("true"))) {

System.out.println("Usage: java SimpleCompiler [filename] [true|false]");

System.exit(0);

}

try {

(new SimpleCompiler()).runCompiler(args[0], args[1].equals("true"));

}

catch(IOException e) {

System.out.println(e.toString());

e.printStackTrace();

}

}

//provided, don't change this

public void runCompiler(String filename, boolean debug) throws IOException {

Node input = fileToQueue(filename);

System.out.println(" Program: " + Node.listToString(input));

if(!debug) {

while(input != null) {

input = compile(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 = compile(input, 1);

System.out.println("----------Lookup BST---------");

System.out.println(symbols);

System.out.println("----------Call Stack--------");

System.out.println(callStack);

if(input != null) {

System.out.println("----------Program Remaining----");

System.out.println(Node.listToString(input));

}

System.out.println(" Press Enter to Continue");

s.nextLine();

}

}

}

}

import java.util. Iterator; class CallStack implements Iterable { // You'll want some instance variables here private Node top; private int size; 80 10 public CallStack() { //setup what you need top = null; size = 0; //create empty stack 11 12 13 14 150 public void push(T item) { //push an item onto the stack 1 / you may assume the item is not null 7/0(1) 17 18 //create a node with item as value Node node = new Node(item); //set current top as next node node.setNext(top); I/if top is not empty, set node as previous top if(top != null) { top.setPrev(node); //set node as new top and update the size top = node; size++; 340 35 36 public T pop() { //pop an item off the stack //if there are no items on the stack, return null 1/0(1) V/if the top null is empty if(top == null) { return null; 37 39 40 //gets data of top node, advance the top node, adjusts links //returns the removed value 43 45 46 47 T data = top.getValue(); top = top.getNext(); if(top != null) { top.setPrev(null); 49 //update size before returning removed value size--; //replace this dummy return statement return data; 53 55 56 57 public T peek() { //return the top of the stack (but don't remove it) //if there are no items on the stack, return null 1/0(1) 58 59 60 61 62 //if the top null is empty if(top == null) { return null; 63 64 //return data to top node T data = top.getValue(); 69 70 71 //replace this dummy return statement return data; 73 740 76 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 1/the stack on the left. 77 79 80 //Hint: Reuse the provided code from another class //instead of writing this yourself! 81 83 1/0(n) 85 87 String data = ""; //calling listToStringBackwards method of Node class to get a string reverse order if(top != null) { data = Node.listToStringBackward(top); 89 //replace this dummy return statement return data; 93 940 95 96 97 98 public void clear() { //remove everything from the stack 1/0(1) top = null; size = 0; 99 100 101 102 103 public int size() { 1/return the number of items on the stack 1/0(1) 104 //replace this dummy return statement return size; 105 106 107 108 109 110 public boolean isEmpty() { //return whether or not the stack is empty 7/0(1) 111 112 113 114 115 116 1170 118 //replace this dummy return statement return size == 0; 119 @SuppressWarnings ("unchecked") public Object[] toArray() { //Return an array representation of the stack. //The top of the stack should be element o //in the array. 1/0(n) 120 121 122 123 124 125 126 127 128 129 Object[]array = new Object[size]; int index = 0; //loop through each node, add data to the array, then return it for (Nodenode = top; node != null; node = node.getNext() { array[index] = node.getValue(); index++; 130 131 //replace this dummy return statement 132 133 134 135 136 137 138 //return top and gets updated return array; 139 public Iterator iterator() { //Return an iterator that traverses from //the top of the stack to the bottom of //the stack. 140 141 142 143 144 145 146 147 148 149 150 151 152 153 0 154 //create iterator object return new Iterator() { //take reference to top Node node = top; //The iterator's hasNext() and next() methods //must both be 0(1) public boolean hasNext() { //a value left as long as node not null return node != null; 155 156 public T next() { /ext() should throw a NullPointerException //throws th exception if there are no more elements if(!hasNext()) { throw new NullPointerException(); 157 158 159 160 161 162 //take data at node, advance node and return data T data = node.getValue(); node = node.getNext(); return data; 163 164 165 public void remove() { 166 167 168 169 170 171 172 //if you try to use next when there are no //more items 173 174 175 //replace this dummy return statement 177 178 179 180 181 public static void main(String[] args) { CallStack s1 = new CallStack(); s1.push("a"); s1.push("b"); 182 183 184 185 CallStack s2 = new CallStack(); s2.push(1); s2.push(2); s2.push(3); 186 if(s1.toString().equals("a b") && s1.toArray ( ) [O].equals("b") && $1. 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"); 187 188 189 190 191 192 193 194 195 196 197 198 199 if(s1.pop().equals("b") && $2.pop().equals(3) && $1.size() == 1 && s2.size() == 2) { System.out.println("Yay 3"); 200 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"); 201 202 203 if(s1.toString().equals("") && $1.peek() == null && s2.peek().equals(1) && $1.pop() == null && s2.pop().equals(1) && s1.size() == 0 && s2.size() == 0) I System.out.println("Yay 5"); 204 205 206 207 208 209 210 s2.push(10); s2.push(20); s2.push(30); if(51. isEmpty() && $1. toArray().length == 0 && !s2.isEmpty()) { s2.clear(); if(s2.isEmpty()) { System.out.println("Yay 6"); 211 212 213 214 215 216 217 218 219 CallStack s3 = new CallStack(); s3.push(3); s3.push(2); s3.push(1); 220 221 222 223 224 int i = 1; for(Integer item: 53) { if(i == item) System.out.println("Yay " + (6+i)); else System.out.println(item); 225 226 227 228 229 i++; } ] 230 51 //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. 3 5 class Node 1 private T value; private Node next; private Node prev; 10 public Node (T value) { this.value = value; DRE } 14 public T getValue() { return value; public void setValue(T value) { this.value = value; public Node getNext() { return this.next; NNNNNNNN public void setNext (Node next) { this.next = next; public Node getPrev() { return this.prev; public void setPrev (Node prev) { 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 n1 = new Node ("A"); Node n2 = new Node ("B"); Node n3 = new Node ("C"); //connect forward references n1.setNext(n2); n2.setNext(n3); //connect backward references n3.setPrev(n2); n2.setPrev(nl); 1/print forward and backward System.out.println (Node.listToString(nl)); System.out.println(Node. listToStringBackward(nl)); import java.util. Iterator; class CallStack implements Iterable { // You'll want some instance variables here private Node top; private int size; 80 10 public CallStack() { //setup what you need top = null; size = 0; //create empty stack 11 12 13 14 150 public void push(T item) { //push an item onto the stack 1 / you may assume the item is not null 7/0(1) 17 18 //create a node with item as value Node node = new Node(item); //set current top as next node node.setNext(top); I/if top is not empty, set node as previous top if(top != null) { top.setPrev(node); //set node as new top and update the size top = node; size++; 340 35 36 public T pop() { //pop an item off the stack //if there are no items on the stack, return null 1/0(1) V/if the top null is empty if(top == null) { return null; 37 39 40 //gets data of top node, advance the top node, adjusts links //returns the removed value 43 45 46 47 T data = top.getValue(); top = top.getNext(); if(top != null) { top.setPrev(null); 49 //update size before returning removed value size--; //replace this dummy return statement return data; 53 55 56 57 public T peek() { //return the top of the stack (but don't remove it) //if there are no items on the stack, return null 1/0(1) 58 59 60 61 62 //if the top null is empty if(top == null) { return null; 63 64 //return data to top node T data = top.getValue(); 69 70 71 //replace this dummy return statement return data; 73 740 76 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 1/the stack on the left. 77 79 80 //Hint: Reuse the provided code from another class //instead of writing this yourself! 81 83 1/0(n) 85 87 String data = ""; //calling listToStringBackwards method of Node class to get a string reverse order if(top != null) { data = Node.listToStringBackward(top); 89 //replace this dummy return statement return data; 93 940 95 96 97 98 public void clear() { //remove everything from the stack 1/0(1) top = null; size = 0; 99 100 101 102 103 public int size() { 1/return the number of items on the stack 1/0(1) 104 //replace this dummy return statement return size; 105 106 107 108 109 110 public boolean isEmpty() { //return whether or not the stack is empty 7/0(1) 111 112 113 114 115 116 1170 118 //replace this dummy return statement return size == 0; 119 @SuppressWarnings ("unchecked") public Object[] toArray() { //Return an array representation of the stack. //The top of the stack should be element o //in the array. 1/0(n) 120 121 122 123 124 125 126 127 128 129 Object[]array = new Object[size]; int index = 0; //loop through each node, add data to the array, then return it for (Nodenode = top; node != null; node = node.getNext() { array[index] = node.getValue(); index++; 130 131 //replace this dummy return statement 132 133 134 135 136 137 138 //return top and gets updated return array; 139 public Iterator iterator() { //Return an iterator that traverses from //the top of the stack to the bottom of //the stack. 140 141 142 143 144 145 146 147 148 149 150 151 152 153 0 154 //create iterator object return new Iterator() { //take reference to top Node node = top; //The iterator's hasNext() and next() methods //must both be 0(1) public boolean hasNext() { //a value left as long as node not null return node != null; 155 156 public T next() { /ext() should throw a NullPointerException //throws th exception if there are no more elements if(!hasNext()) { throw new NullPointerException(); 157 158 159 160 161 162 //take data at node, advance node and return data T data = node.getValue(); node = node.getNext(); return data; 163 164 165 public void remove() { 166 167 168 169 170 171 172 //if you try to use next when there are no //more items 173 174 175 //replace this dummy return statement 177 178 179 180 181 public static void main(String[] args) { CallStack s1 = new CallStack(); s1.push("a"); s1.push("b"); 182 183 184 185 CallStack s2 = new CallStack(); s2.push(1); s2.push(2); s2.push(3); 186 if(s1.toString().equals("a b") && s1.toArray ( ) [O].equals("b") && $1. 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"); 187 188 189 190 191 192 193 194 195 196 197 198 199 if(s1.pop().equals("b") && $2.pop().equals(3) && $1.size() == 1 && s2.size() == 2) { System.out.println("Yay 3"); 200 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"); 201 202 203 if(s1.toString().equals("") && $1.peek() == null && s2.peek().equals(1) && $1.pop() == null && s2.pop().equals(1) && s1.size() == 0 && s2.size() == 0) I System.out.println("Yay 5"); 204 205 206 207 208 209 210 s2.push(10); s2.push(20); s2.push(30); if(51. isEmpty() && $1. toArray().length == 0 && !s2.isEmpty()) { s2.clear(); if(s2.isEmpty()) { System.out.println("Yay 6"); 211 212 213 214 215 216 217 218 219 CallStack s3 = new CallStack(); s3.push(3); s3.push(2); s3.push(1); 220 221 222 223 224 int i = 1; for(Integer item: 53) { if(i == item) System.out.println("Yay " + (6+i)); else System.out.println(item); 225 226 227 228 229 i++; } ] 230 51 //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. 3 5 class Node 1 private T value; private Node next; private Node prev; 10 public Node (T value) { this.value = value; DRE } 14 public T getValue() { return value; public void setValue(T value) { this.value = value; public Node getNext() { return this.next; NNNNNNNN public void setNext (Node next) { this.next = next; public Node getPrev() { return this.prev; public void setPrev (Node prev) { 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 n1 = new Node ("A"); Node n2 = new Node ("B"); Node n3 = new Node ("C"); //connect forward references n1.setNext(n2); n2.setNext(n3); //connect backward references n3.setPrev(n2); n2.setPrev(nl); 1/print forward and backward System.out.println (Node.listToString(nl)); System.out.println(Node. listToStringBackward(nl))