[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]

COMP2100/2500
Lecture 7: Recursive Data Types II

Summary

The second lecture in our study of recursive data structures, focusing on the implementation of stacks and expression trees.

Aims

• Demonstrate the use of inheritance to avoid redundant attributes and dangerous switch instructions in recursive data types.

Outline

1. Expression, version 3

2. Using Expression, version 3

3. Assessment of Expression, version 3

4. Stack, version 3

5. Using Stack, version 3

6. Using a StackFactory

---

Expression (Version 3)

The idea here is to avoid having to declare all possible attributes in every type of expression, and also to avoid the explicit case-by-case programming we saw in Expression Versions 1 & 2:

• Constants don't need left and right subtrees

• Negations only need one subtree

• None of the operations needs to store an integer ‘constant value’.

Expression is now an interface (it could be also made an abstract class, but if we need no even partial implementation, the interface version is preferable because it has greater flexibility) and the different types of expressions are subclasses, which implement the Expression interface.

public interface Expression3 {

    /** The value of this expression */
    public int getValue();
    
    /** Pretty infix string representation */
    public String toString();
}

---

Now for the subclasses.

public class Constant3 implements Expression3 {

    /** The value */
    private int value;

    /** Initialise value */
    public Constant3(int v) {
	value = v;
    }

    /** The value of this expression */
    public int getValue() {
	return value;
    }

    /** Pretty infix string representation */
    public String toString() {
	return "" + value;
    }
}

---

public class Addition3 implements Expression3 {

    /** The sub-expressions being added */
    private Expression3 left, right;

    /** Initialise left and right sub-expressions */
    public Addition3(Expression3 l, Expression3 r) {
	left = l;
	right = r;
    }

    /** The value of this expression */
    public int getValue() {
	return left.getValue() + right.getValue();
    }

    /** Pretty infix string representation */
    public String toString()  {
	return "(" + left.toString() + " + " +
	    right.toString() + ")";
    }
}

Classes Multiplication, Subtraction and Negation are just variations on this theme.

---

Using Expression (Version 3)

Build this expression in e, and evaluate:

	Expression3 a, b, c, d, e;

	a = new Constant3(1);
	b = new Constant3(2);
	c = new Addition3(a, b);
	a = new Constant3(3);
	b = new Constant3(4);
	d = new Addition3(a, b);
	e = new Multiplication3(c, d);

	System.out.println(e.toString() + " = " + e.getValue());

---

Assessment of Expression (Version 3)

+ Conceptually simple

+ No subtle manipulation of object references

+ Construction process is symmetric

+ Each expression type has only relevant attributes

+ Different behaviour of routines is separated by type. (No more case-by-case programming with switch or if-then-else statements branching on the value of type.)

+ Easy to expand (division, exponentiation,...)

+ Easy to maintain

Version 3 is a significant improvement over Versions 1 and 2.

---

Stack Implementation (Version 3)

Let's do the same thing to the Stack.

public abstract class Stack3<A> {

    /** Is this stack empty? */
    public abstract boolean isEmpty();
    
    /** The top element */
    public abstract A top();
    //require !isEmpty()

    /** The result of removing the top element */
    public abstract Stack3<A> pop();
    // require !isEmpty()

    /** The number of elements stored */
    public int depth() { return 0; }
}

---

Notice the contracts in the deferred features, and the partial implementation (i.e. the body of depth).

We need two subclasses, one for empty stacks (!?) and one for all the other ones. Empty stacks are pretty simple...

public class EmptyStack3<A> extends Stack3<A> {
    public EmptyStack3() {}
    public boolean isEmpty() { return true; }
    public Stack3<A> pop() { return null; }
    public A top() { return null; }
    public int depth() { return 0; }
}

Non-empty stacks are simplified too, since all the questions are answered already.

public class NonemptyStack3<A> extends Stack3<A> {

    private A value;
    private Stack3<A> rest;

    /** Initialise by pushing */
    public NonemptyStack3(A x, Stack3<A> s) {
	value = x;
	rest = s;
    }

    public boolean isEmpty() { return false; }
    public A top() { return value; }    
    public Stack3<A> pop() { return rest; }
    public int depth() { return 1 + pop().depth(); }
}

---

Using Stack (Version 3)

Stack3<Integer> s;

s = new EmptyStack3<Integer>();
s = new NonemptyStack3<Integer>(1, s);
s = new NonemptyStack3<Integer>(2, s);
s = new NonemptyStack3<Integer>(s.top() + s.pop().top(),
                                      s.pop().pop());

Ease of use is hindered by long constructor names and the necessity to specify the type in each creation.

---

Using a StackFactory

We can simplify this by creating a new ‘factory’ class to build stacks of a nominated type:

public class StackFactory<A> {

    /** A brand new empty stack */
    public Stack3<A> empty() {
	return new EmptyStack3<A>();
    }
    
    /** The result of a push */
    public Stack3<A> push(A x, Stack3<A> s) {
	return new NonemptyStack3<A>(x, s);
    }
}

---

Now the code to build and process our example expression is a little easier to type.

StackFactory<Integer> sf;
Stack3<Integer> s;

sf = new StackFactory<Integer>();

// Now either build the stack in stages
s = sf.empty();
s = sf.push(1, s);
s = sf.push(2, s);

// or do the whole thing in one line
s = sf.push(2, sf.push(1, sf.empty()));

s = sf.push(s.top() + s.pop().top(), s.pop().pop());
System.out.println("Depth = " + s.depth());
System.out.println("Top   = " + s.top());

---

A Deficiency with Expression Version 3

It is easy to add a new kind of expression e.g., division or exponentiation. (How? Just create a new subclass of Expression3.)

But what if we wanted a new operation to apply to expressions? For example:

• size(): The size of the expression tree.

• postfix(): Postfix string representation.

To add size, we would have to:

• Add an abstract description of size() to class Expression3

• Add an implementation of size() to each subclass: Constant, Addition,...

The more different kinds of expressions there are, the more work this will be.

Worse, if Expression3 were a library class, we couldn't modify it!

[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]