CSE 326 – Data Structures – Winter 2002

Homework #3 – Trees

Due Friday, Feb. 1, 2002
Written material – proofs, plots, discussion, etc., - hand in hardcopy in class

Programs – use electronic turn-in, following instructions for program turn-in and documentation on the course web page – by start of class that day

 

Goals of this assignment:

 

This assignment may be done in teams of 2 or 3 people (recommended).  All will receive the same grade.  Include everyone’s name on both the electronic turn-in and hardcopy materials. 

 

For this assignment you need only implement the parts of the necessary classes and methods that you will actually use.

 

1.  Nested lists (also called multi-lists) are a universal data structure that can be used to implement nearly all of the other linked data structures we will discuss in this course.

 

A “symbolic expression”, or SEXPR for short, is a datatype can represent an integer, a string, or a list of SEXPR’s.  Define a SEXPR class.  Its private data should include a union structure that can contain any of those kinds of elements, along with a variable that indicates what kind of information is stored in the SEXPR.  Write public methods for accessing the data and determining its type.

 

You will instantiate the LIST class you created in the first assignment to create the “list of SEXPR’s” type.

 

Write input and output procedures for SEXPR’s.  These may be defined as methods, overloaded operators, or just plain, good old fashioned global functions.  For this assignment coming up with a nice algorithm is more important than maintaining strict “C++ style”.  It is likely that your I/O functions will be easiest to write using recursion.

 

For input and output a string is any sequence of characters not containing whitespace or a parenthesis that is not a legal integer.  For example, the list

                        (bad   16cat99   -123)

contains two strings “bad” and “16cat99” and an integer -123.  (Think: how can you quickly determine if a string only contains an optional ‘-‘ sign followed by the characters ‘0’ through ‘9’?  Remember the “switch” statement.)

 

Create a program called

                        sexpr

that simply reads SEXPR’s from stdin and prints them to stdout until end of file is reached.  Print an end of line after each SEXPR printed.  For example, given the input:

 

(cat                  (999      is

         ) in 24  (    bag  ) )       16   (32    now ) 

justaverylongstring

 

Your program would print:

 

(cat (999 is) in 24 (bag))

16

(32 now)

justaverylongstring

 

Do not have a memory leak in your code:  if you read in a new SEXPR into a variable containing an old one, be sure to deallocate the old SEXPR and everything it contains.

 

2.  Compilers and interpreters represent expressions as trees, as discussed in the class and the textbook (section 4.2.2).  In an expression tree a node is labeled with the name of function, and the children of the node are the arguments to the function.

 

Although ugly and barbaric programming languages like C++ use a bizarre mix of prefix, infix, and postfix notation for the textual representation of a program, with subtle and complicated rules for operator precedence, elegant functional programming languages like LISP or Scheme use only prefix notation and require fully-parenthesized expressions.

 

 For example, the C++ expression

                        (1 + 2 * 3) +((4 * 5 + 6) *  7)

would be written in LISP as

                        (PLUS (PLUS 1 (TIMES  2  3)) (TIMES  (PLUS  (TIMES  4  5)  6)  7))

One beautiful aspect of LISP notation is that the nested list structure is the expression tree, using the convention that the first item in a list is the name of a function, the second item is the left subtree, and the third item is the right subtree.)

 

Write a program called

                        evaluate

that repeatedly reads a SEXPR from stdin, evaluates it as an expression tree, and then writes the result to stdout (followed by a newline).  Keep reading and evaluating expressions until you reach the end of input.  The expressions may contain the functions PLUS, MINUS, TIMES, and DIVIDE, where the last is integer division (e.g. 3/2 = 1).

 

3.  What good is a programming language without variables?  Extend your interpreter to handle expressions of the form

                        (SET   VARIABLE   VALUE)

where VARIABLE is any string, and value is a SEXPR.  The result of evaluating this expression is to store the association between the variable and the value in a symbol table.   Then, when you are evaluating a SEXPR that turns out to be a string rather than a list or an integer, you look up the value of the variable in the symbol table.  (If the variable does exist in the symbol table print an error message and quit.)

 

You should implement your simple table as a binary search tree.  Now you have a choice:  you can  (1)  write new code for binary search trees, (2) borrow and modify code from the Weiss textbook, or (3) use SEXPR’s to represent a binary search tree.  For example, you could use a SEXPR of the form

                        (VARIABLE   VALUE   LEFT_SUBTREE  RIGHT_SUBTREE)

In this case you’ll need to add methods to your SEXPR class or LIST template that allow you to modify the elements in a list  (for example, when a new node is inserted in the tree, or the value of a variable changes).

 

In any case you only need to implement the actual methods you need to use.  So, for example, you need to be able to add and modify elements in the binary search tree, but you never need to actually delete one – variables are never removed from the symbol table.  Likewise you don’t have to worry about destructors or copy operators for your binary search tree.

 

Add this code to your “evaluate” program, which should otherwise work as before.

 

4.  OPTIONAL BONUS!  This next part is not required.  If you do it you receive bonus points above and beyond the ordinary points for the assignment.  These bonus points can be used to make up for less-than-perfect performance on other assignments and exams, according to an arcane and secret formula that national security considerations preclude me from revealing at this time.  However, if as a result of bonus points your final grade is greater than 4.0, you will receive a free letter of recommendation to the graduate school of your choice.

 

Programming languages are more fun if they include loops.  Extend your interpreter to handle expressions of the form:

                        (WHILE   CONDITION   BODY)

Both CONDITION and BODY are SEXPR’s.  This form evaluates CONDITION, if it is greater than 0 it evaluates  BODY, and then repeats.   In addition to your program provide two files that contain SEXPR’s that do the following:

 

            1.  A file named “factorial” that computes 6! when fed into “evaluate”.

            2.  A file named “fibonacci” that computes the 6th Fibonacci number when fed into “evaluate”.