CS 68 Spring 2011Homework 8Due Wednesday, 5/27/2011Please turn in your written homework solutions, program listings, and test runs before the b e ginningof class on the due date and put your programming solutions in the dropbox on Blackboard.1. (15 points) Like Current in EiffelPlease do problem 12.8 from Mitchell, page 376.2. (15 points) Expression ObjectsWe now look at an object-oriented way of representing arithmetic expressions given by the gram-mare ::= num | e + eWe begin with an “abstract class” called SimpleExpr. While this class has no instances, it liststhe operations common to all instances of this class or subclasses. In this case, it is just a singlemethod to return the value of the expression.abstract class SimpleExpr {abstract public int eval();}Since the grammar gives two cases, we have two subclasses of SimpleExpr, one for numbers andone for sums.public class Number extends SimpleExpr {private int n;public Number(int n) { this.n = n; }public int eval() { return n; }}public class Sum extends SimpleExpr {private SimpleExpr left, right;public Sum(SimpleExpr left, SimpleExpr right) {this.left = left;this.right = right;}public int eval() { return left.eval() + right.eval(); }}(a) Product ClassExtend this class hierarchy by writing a Times class to represent product expressions of theforme ::= . . . | e ∗ e1CS 68 Spring 2011(b) Method CallsSupp ose we construct a compound expression bySimpleExpr a = new Number(3);SimpleExpr b = new Number(5);SimpleExpr c = new Number(7);SimpleExpr d = new Sum(a,b);SimpleExpr e = new Times(d,c);and send the message eval to e. Explain the sequence of calls that are used to compute thevalue of this expression: e.eval(). What value is returned?(c) Comparison to “Type Case” constructsLet’s compare this programming technique to the expression represe ntation used in Haskell,in which we declared a data type and defined functions on that type by pattern matching.The following eval and toString functions illustrate one form of a “type case” operation,in which the program inspects the actual tag (or type) of a value being manipulated andexecutes different code for the different cases:data HaskellExp = Number Integer | Sum (HaskellExp, HaskellExp)eval:: HaskellExp -> Integereval (Number(x)) = xeval (Sum(e1,e2)) = eval(e1) + eval(e2)toString:: HaskellExp -> StringtoString(Number(x)) = show xtoString(Sum(e1,e2)) = toString(e1) ++ " + " ++ toString(e2)This idiom also come s up in class hierarchies or collections of structures where the program-mer has included a Tag field in e ach definition that encodes the actual type of an object.i. Discuss, from the point of view of someone maintaining and modifying code, the dif-ferences between adding the Times class to the object-oriented version and adding aTimes constructor to the HaskellExpr data type. In particular, what do you need toadd/change in each of the programs. Generalize your observation to programs containingseveral operations over the arithmetic expressions, and not just eval and toString.ii. Discuss the differences between adding a new operation, such as prettyPrint (toStringis pretty lame, not introducing any parenthesization), to each way of representing ex-pressions. Assume you have already added the product representation so that there ismore than one class with nontrivial eval methods.3. (25 points) Visitor Design PatternThe extension and maintenance of an object hierarchy can be greatly simplified (or greatly com-plicated) by design decis ions made early in the life of the hierarchy. This question builds on theprevious question in exploring design pos sibilities for an object hierarchy representing arithmeticexpressions.The designers of the hierarchy have already decided to structure it as shown below, with a baseclass Expr and derived classes Number, Sum, Times, and so on. They are now contemplating how2CS 68 Spring 2011to implement various operations on Expressions, such as printing the expression in parenthesizedform or evaluating the expression. They are asking you, a freshly-minted language expert, to help.The obvious way of implementing such operations is by adding a method to each class for eachoperation. The Expression hierarchy would then look like:public interface Expr {public String toString();public int eval();}public class Number implements Expr {private int n;public Number(int n) { this.n = n; }public String toString() { ... }public int eval() { ... }}public class Sum implements Expr {private Expr left, right;public Sum(Expr left, Expr right) {this.left = left;this.right = right;}public String toString() { ... }public int eval() { ... }}Supp ose there are n subclasses of Expr altogether, each similar to Number and Sum shown here.How many classes would have to be added or changed to add each of the following things?(a) A new class to represent product expressions.(b) A new operation to graphically draw the expression parse tree.Another way of implementing expression classes and operations use s a pattern called the VisitorDesign Pattern. In this pattern, each operation is represented by a Visitor class. Each Visitorclass has a visitClass method for each expression class Class in the hierarchy. Each e xpressionclass Class is set up to call the visitClass method to perform the operation for that particularclass. In particular, e ach class in the expression hierarchy has an accept method which acceptsa Visitor as an argument and “allows the Visitor to visit the class and perform its operation.”The expression class does not need to know what operation the visitor is performing.If you write a Visitor class ToString to construct a string representation of an expression tree, itwould be used as follows:Expr expTree = ...some code that builds the expression tree...;ToString printer = new ToString();String stringRep = expTree.accept(printer);System.out.println(stringRep);3CS 68 Spring 2011The first line defines an expression, the second defines an instance of your ToString class, andthe third passes your visitor object to the accept method of the expression object.An Eval visitor might work similarly, but evaluating an expression rather than converting it to astring.The expression class hierarchy using the Visitor Design Pattern has the following form, with anaccept method in each class and poss ibly other methods. Since different kinds of visitors returndifferent types of values, the accept method is parameterized by the type that the visitor computesfor each