//This program demonstrates a StringTokenizer, which is a class used to //break up a String into "tokens." There are actually 2 demos // - one which treats "white space" as delimiters and finds tokens // - one which defines its own delimiters and also returns them as tokens. // Specifically, the second example breaks up mathematical expressions. //You can comment out a test if you want to see them one at a time...

import java.io.*; import java.util.*; import java.util.StringTokenizer; /eeded for StringTokenizer

public class TokenizerDemo { public static void main(String args[]) throws IOException { //read in a String that we will tokenize Scanner kb = new Scanner(System.in); String inputLine; System.out.println("Please enter input line: "); String input = kb.nextLine();

StringTokenizer tokenizer; /* //============================================= //DEMO1: a regular StringTokenizer breaking it up into words ("tokens") System.out.println(" This demo breaks up a String into tokens");

tokenizer = new StringTokenizer(input); //create a new StringTokenizer for that line

System.out.println("The number of tokens will be: " + tokenizer.countTokens());

while(tokenizer.hasMoreTokens()) { String token = tokenizer.nextToken(); System.out.println("Next token is to be processed is: " + token); }

*/ //========================================================== //DEMO2: a regular StringTokenizer setting a comma as the delimiter System.out.println(" This demo breaks up a number into tokens");

tokenizer = new StringTokenizer(input, ","); //create a new StringTokenizer for that line

System.out.println("The number of tokens will be: " + tokenizer.countTokens()); while(tokenizer.hasMoreTokens()) { String token = tokenizer.nextToken(); System.out.println("Next token is to be processed is: " + token); System.out.println("as an int, the next token is: " + Integer.parseInt(token)); } /* //================================================== //DEMO3: using math symbols as tokens ------------------------------ System.out.println(" This demo3 breaks up a math expression into tokens"); tokenizer = new StringTokenizer(input, "()+-/*%", true);

while(tokenizer.hasMoreTokens()) { String token = tokenizer.nextToken(); System.out.println("Next token is to be processed is: " + token); } */ } }

import java.util.*; public class DLList { //-------- data private DLLNode head; private DLLNode tail; //-------- constructors public DLList() { head = null; tail = null; }

//-------- methods public String toString() { DLLNode cursor = head; String str = ""; while (cursor != null) { if (str.isEmpty()) { str = str + cursor.data; } else { str = str + ", " + cursor.data; } cursor = cursor.next; } return "[" + str + "]"; }

//backwards - this will traverse the list like toString, only "backwards". public String backwards() { DLLNode cursor = tail;//start from the tail String str = ""; while (cursor != null) { if (str.isEmpty()) { str = str + cursor.data; } else { str = str + ", " + cursor.data; } cursor = cursor.prev;//traverse back using the prev pointer } return "[" + str + "]"; }

//addLast - adds a new DLLNode to the end of the list public void addLast(E theData) { //create the new DLLNode DLLNode aNode = new DLLNode(theData); //Case1: the list was empty (head was null). Change links if (head == null) { head = tail = aNode; } //Case2 and 3: list has 1 or more elements. Change links else { tail.next = aNode; //put it on the end aNode.prev=tail;// the new node aNode points to the last node in the Doubly linked list tail = aNode; /ow aNode is at the end (tail) } }

//isEmpty - returns true if the list is empty public boolean isEmpty() { return head == null; }

//------------------------------------------------------ //addFirst - adds to the front of the list public void addFirst(E someData) { //create a new DLLNode DLLNode aNode = new DLLNode(someData); //Case1: is list empty? if (head == null) { head = tail = aNode; } //Case2,3: is has >=1 element already else { aNode.next = head; head.prev=aNode;//the first node becomes second and points to the new node aNode head = aNode; } }

//getFirst - returns the element at the front of the list, without deleting public E getFirst() { //case1: empty list if (head == null) { throw new NoSuchElementException("can't getFirst from empty list"); } //case 2,3: list has 1 or more elements - return data that head points at return head.data; }

//getLast - returns the element at the end of the list, without deleting public E getLast() { //case1: empty list if (head == null) { throw new NoSuchElementException("can't getLast from empty list"); } //case 2,3: list has 1 or more elements - return data that tail points at return tail.data;

}

//removeFirst - returns the element at the front of the list and deletes it public E removeFirst() {

//case1: list is empty if (head == null) { throw new NoSuchElementException("can't removeFirst from empty list"); } //case2: 1 element on the list else if (head == tail) { E savedData = head.data; //save the data head = tail = null; return savedData; } //case3: many elements on list else { E savedData = head.data; head = head.next;//make the second node first in the list head.prev=null;//make the new head's previous point to null return savedData;

}

}

//removeLast - returns the element at the end of the list and deletes it public E removeLast() { //case1: list is empty if (head == null) { throw new NoSuchElementException("can't removeLast from empty list"); } //case2: list has 1 element else if (head == tail) { return removeFirst(); //or could have same 3 statements as removeFirst does } //case3: list has many elements else { //save the last data so we can return it E savedData = tail.data; //make the second last node, last node in the list tail=tail.prev; tail.next=null;//make the new tail's next point to null //return it return savedData; } }

//size - returns the number of elements in the list public int size() { /eeds a counter int count = 0; //declare a cursor that will "walk" through the list DLLNode cursor = head; //as long as ("while") cursor is not null, count it while (cursor != null) { count++; cursor = cursor.next; //move to the next node... } return count; }

//contains - returns true if the list contains what is received, false otherwise public boolean contains(E elt) { //create a cursor so we can "walk" through the list DLLNode cursor = head; //walk through the whole list (maybe) while (cursor != null) { if (cursor.data.equals(elt)) //found it! { return true; } cursor = cursor.next; } //if we get all the way through the list, we did not find it return false; }

//add - adds a new element at the given index. // throws IllegalArgumentException if the index is out of bounds public void add(int index, E elt) { //check to see if the index is out of bounds if (index size()) { throw new IllegalArgumentException("index " + index + " is out of bounds"); } //create a new node that holds elt DLLNode aNode = new DLLNode(elt); //case1: list is empty if (head == null) { head = tail = aNode; } //case2,3: here, index is 0 so putting it at the front else if (index == 0) { addFirst(elt); //creates a new node and puts it at front } //index is same as size() so putting it at the end else if (index == size()) { addLast(elt); } //if we get to here, we know that it is going onto the list at a //legal index and not at the front or the back else {

//find the node in front of where it goes... DLLNode cursor = head;

for (int i = 0; i

} } //remove - removes and returns the first occurrance of an element. // returns true if successful, false otherwise public boolean remove(E elt) { //case1: list is empty if (head == null) { return false; } //case2: list has 1 element - one element to check else if (head == tail) { if (head.data.equals(elt)) { removeFirst(); return true; } else { return false; } } //case3: list has many elements else { //check to see if the list even contains it... if (!contains(elt)) { return false; } //if we get to here, we know the list contains it //check to see if it is the first element... else if (head.data.equals(elt)) { removeFirst(); return true; } //if we get to here, we know the list contains it //and it is not the first element //so we can find the node in front of it (since not first) else { DLLNode cursor = head; //move cursor, stopping at the node in front of one to be removed while (!cursor.next.data.equals(elt)) { cursor = cursor.next; }

//cursor should have stopped at the node before the one to be removed //if the node to be removed was the last one... if (cursor.next == tail) { removeLast(); } //otherwise, make the link go around it else { cursor.next = cursor.next.next; cursor.next.prev=cursor;//make the next of cursor point to cursor as previous node } return true; } } }

//================================= //This class will implement a node in our doubly linked list class DLLNode { //data

protected E data; //(protected here so we can say things like head.next) protected DLLNode next; /ext points at another node protected DLLNode prev; //prev points at another node //constructors

public DLLNode(E theData) { data = theData; next = null; prev = null;//make the previous pointer point to null } //methods //toString - returns its representation as a String

public String toString() { return "" + data; } }

CSC205AB Program3: Infinite Int Background: Please use the doubly linked list you developed (DLList.java). Let me know if you do not have one and I will provide one for you. As you conceptualize the program, you will see why a doubly linked list is used. The Program: Write a new class called Infinite Int. We can (theoretically) store an "infinite" integer by linking together nodes that hold actual complete integers. So it will look like this: head tail Complete 32-bit int Complete 32-bit int Complete 32-bit int For this program, just store 3 digits in each node (concept is the same, but we won't have to generate hundreds of digits to test it). For example, the integer 487,021,639 will be stored like this: head tail 21. 639 As you can see, it uses a doubly linked list; therefore, make your Infinite Int class a subclass of a DLList that holds Integers. Be sure that all of DLList's data (head and tail) can be inherited from the superclass. Since it also will have to have a compareTo (see requirements below), your InfiniteInt should be defined as: public class InfiniteInt extends DLList implements Comparable Since your Infinite Int is a subclass of DLList, it will inherit DLList's methods, but you will also have to implement the following methods/constructors: A default constructor that takes no arguments and just builds a "null" linked list (it could call its super which just sets head and tail to null). CSC205AB Program3: Infinite Int Background: Please use the doubly linked list you developed (DLList.java). Let me know if you do not have one and I will provide one for you. As you conceptualize the program, you will see why a doubly linked list is used. The Program: Write a new class called Infinite Int. We can (theoretically) store an "infinite" integer by linking together nodes that hold actual complete integers. So it will look like this: head tail Complete 32-bit int Complete 32-bit int Complete 32-bit int For this program, just store 3 digits in each node (concept is the same, but we won't have to generate hundreds of digits to test it). For example, the integer 487,021,639 will be stored like this: head tail 21. 639 As you can see, it uses a doubly linked list; therefore, make your Infinite Int class a subclass of a DLList that holds Integers. Be sure that all of DLList's data (head and tail) can be inherited from the superclass. Since it also will have to have a compareTo (see requirements below), your InfiniteInt should be defined as: public class InfiniteInt extends DLList implements Comparable Since your Infinite Int is a subclass of DLList, it will inherit DLList's methods, but you will also have to implement the following methods/constructors: A default constructor that takes no arguments and just builds a "null" linked list (it could call its super which just sets head and tail to null)