x Programming Assignment 2 Computer Science 102

Programming Assignment 2

Computer Science 102

Spring 2003

First draft due THUR, FEB 26, 11:59 pm (midnight). Each successive draft is due one week after the due date for the previous draft .

Your project is to design a program to implement string operations. You will impliment this in two ways, the first using linked lists that you construct, and the second, using a LinkedList and Iterator class that you write.

Recall that in Java there is already a String class. A String is a linked list of characters, plus a node that indicates how many characters are being stored. You are to implement an alternative string class, called StringADT, that does not store the length -- it will be determined by one of the methods --it just stores each character in a node whose info field is of type Object in a linked list.

For example, to represent the string 'comp', you can use the following linked list.

        _______     ______     ______     ______
list--> |_C|___|--> |_O|__|--> |_M|__|--> |_P|__|-->null

The first draft consists of two classes:
  1. A StringADT class that will implement several string operations,
  2. A client class that will act as a driver for the StringADT class. Do not write this class; it's given on the web.

The StringADT class

In the class StringADT, you will implement an abstract data type, that will allow several useful string operations. The interface that this class will implement is given below and is also a link on the homepage that you will be able to download.

public class StringADT
 public void concat(StringADT list1, StringADT list2) 
//Precondition: the lists exist or are null.

/*Postcondition: the implicit parameter this points to the
concatenation of list1 and list2; the nodes of the conatenated are separate
from the nodes of list1 and list2.*/

public void copy(StringADT list1 );
//Precondition:  the list exists or is null .
//Postcondition:  this points to a a copy of list1.  
//The nodes of the copied list are separate from the nodes of list1.

public void repeats(StringADT list1 ,int n); 
//Precondition: n >= 0.
/*Postcondition: this points to the concatenation of n copies of
list1.  If n = 0, then the copied list is the empty string represented by a
linked list consisting of only the null pointer.*/

public assign(String list1);
//Precondition: None.  (Notice that list1 is a Java string.)
//Postcondition: this points to the link list
//representing the string as list1.

public substring(StringADT list1 ,int x, int y):

//Precondition: 0<= x <= y < leng(list1).  
/*Postcondition: this points to the link list representing the
substring of list1 that goes from the xth indexed character to the yth indexed

public int leng(StringADT  list1)
{Precondition: None.
 Postcondition: Returns the number of characters of list1.}

public Print(StringADT list1);
//Precondition: list1 exists or is null
//Postcondition: Displays the characters of list1 on the terminal. 

//private Link head;
//This cannot be included in the interface

Encapsulation dictates that the class's field be declared private. Thus the private field cannot be used as a parameter for the methods of the object; however as we see here, the object -- list1 -- can. Also, the private field cannot be included in the ADT -- an interface cannot contain variables. However, you must include it in your StringADT class in your program. When you finish your StringADT class and have implemented all the methods, change the public class statement so that it ends with implements ADT, e.g., public class StringADT implements ADT. Once you indicate that your class implements the interface, all of its methods must be included in your StringADT class, so it you implement the iterface when you are developing your methods, you should supply dummies for the methods not yet written.

Draft 1

For draft 1, you are required to first write a class called StringADT which contains as methods the usual string operations: assignment (x = "nyu"), concatenation (z = x + y), multiplication (w = 12 * z), substring (w = x [2,5]), copying (u = x), and printing. These operations are to be implemented with linked lists. The private field of the class is a pointer to a linked list.

When you write the methods, remember that when you assign null to a pointer, you are assigning a new address to the pointer. What happens if Link p = new Link() and then q.next = p is executed? The answer is that p is the address stored in q.next. If another p = new Link() is executed, q.next is still the address stored in the old p. If p = null is executed instead, q.next is still the address stored in the old p and not null.

An example of a method heading is public assignment( StringADT st1); So if st1 is "nyu", the implicit parameter this is the object that contains the pointer to the first node of the three node linked list containing 'n', 'y', and 'u'. The object is defined and implemented in class StringADT. There is a class tester.java (available on the homepage) that checks your StringADT.

Draft 2 (due THURS night MAR 6)

Please note that the midterm will be on MON MAR 10 in your usual class room.

Rewrite StringADT so that it envokes the LinkedList and Iterator classes described on the feb19 link. This actually makes the programming easier to write. For instance, the assign method, absent the test for an empty string, becomes:

public void assign(String s)
    LinkedList list = new LinkedList();
    char ch;
    int len = s.length();
    for(int j = 0; j< len; j++)
	ch = s.charAt(j);
        list.addLast(new Character(ch) );
    this.head = list;
where head is now of type LinkedList.

The concat method uses two instances of iterators driving two loops. The repeats method nests an iterator while loop in for loop.

Use the same tester.java you used to test draft #1 to test this draft.

Draft 3 Due THUR night, MAR 27, 11:59 pm

This draft consists of a string interpreter into which the user inputs a file available on the web with a series of string commands. After each command, your program will parse the command and then print out its result. Each command will have one of the following forms:

  1. x = "Hello"
  2. x = y + z
  3. x = y
  4. x = 17 * y
  5. x = y [10,20]
  6. length x
  7. x
  8. quit

Here x, y, and z represent string variables (possibly the same variables). The only variable names allowed will be a single character, either a lowercase letter ('a' to 'z') or an uppercase letter ('A' to 'Z'). Unlike Java, an uppercase letter refers to the same variable as its lowercase counterpart.

Each of the tokens in the input line will be separated by one or more blanks. The front end of the interpreter, called the lexical analyser, uses this fact to separate the tokens,

If one of the variables on the right side of an assignment has not been initialized, your class should complain and skip that line. Use a symbol table to keep track of those variables assigned values. Also, the actual StringADT parameters should be elements of an array of StringADT.

Discussion and explanation
If the input to the interpreter is:

x = "nyu"
y= "hello"
z = y + x
where z is the instruction to print the string stored in z, then the result would be "hellonyu".

The lexical analyser breaks the input into constituent parts called tokens. Then the next part of the interpreter, called the parser, determines which statement (assignment, print, etc.) a line of token represents. I have written the lexical analyser, also called the scanner, for you, and the initial stage of the parser (again, these are available on the homepage in analyse.pas). Because the tokens in the input are separated by at least one blank, the scanner is an elementary one. The parser indicates which method further parses a statement. The parsing up to this point is done simply by determining how many tokens appear in the input. Thus x = "hello" and x = y are parsed such that the same method is executed. It is up to you to further parse them by distinguishing between an assignment and a copy statement.

Use a symbol table to check whether a variable that must have a value in any operation, has in fact been assigned a value. This in x = y, you would check whether y has been assigned a value. Do this by using a globally declared array static boolean[] symbolTable, where the dimension of the array is 26. If the input contains an undefined variable, the interpreter must print an error message.

How do you associate a variable with the pointer to the linked list? The natural way is to have an array of the object, i.e., static StringADT[] table. Assume that if x = "nyu" and y = "hello"; and Px is the pointer to the linked list for x; and Py, for y, then Table['X'] contains Px and Table['Y'] contains Py.

How is this implemented? For instance in x = "nyu", stream[0] is "x", stream[1] is "=" and stream[2] is the string "nyu". First you must strip the quotes from "nyu". The quotes are the first and last elements of stream[2]. These are referred to as stream[2].charAt(0) and stream[2].charAt(4) respectively. The element of table is the implicit parameter of method assign. Remember that the header for the method is: public assign( String st). In order to have the pointer for the linked list that stores "nyu" being the contents of the element 'X' of Table, you must write:


where stripped is the assigned string with its quotes deleted (here, nyu); variable is the first character of stream[0] converted to an uppercase char variable; and sADT is the instance of StringADT. We subtract 'A' from variable in the brackets because we want the variable A to correspond to the zeroth element of table.

Here are some methods you might find usefull: