/* Expression tree, "csc17" version. We use interfaces and inheritance to implement three classes of expressions: for integers, for +, and for * expressions. Each expression subclass will implement just what it needs to. These "algebraic types" illustrate the potential for oop languages to achieve a new approach to program organization altogether. We also add one final refinement: use inheritance to allow code sharing between + and * operator subclasses. Class "operatornode" is the superclass for both timesnode and plusnode. Note that the superclass doesn't implement the expr interface, since without knowing the type of the operator, it won't know how to eval an expression. */ using System; public interface expr // abstract interface for all expression trees { int eval(); void print(); } class intnode : expr // integer expreesion, or leaf nodes { int val; public intnode(int v) {val = v; } public int eval() { return val; } public void print() { Console.Write(val); } } // intnode class operatornode // interior node superclass for code sharing { public expr left, right; // type of subtrees is "expr", not "node"! public operatornode(expr l, expr r) { left=l; right=r; } protected void print(String op) { Console.Write("("+op+" "); left.print(); Console.Write(" "); right.print(); Console.Write(")"); } } //operatornode superclass class plusnode : operatornode, expr // + operator expression { public plusnode(expr l, expr r) : base(l,r) {} public int eval() { return left.eval() + right.eval(); } public void print() { base.print("+"); } } // plusnode class timesnode : operatornode, expr // * operator expression { public timesnode(expr l, expr r) : base(l,r) {} public int eval() { return left.eval() * right.eval(); } public void print() { print("*"); } //"base" is not needed (overloading) } // timesnode public class exptree3 { public static void Main() { expr A = new plusnode(new timesnode(new intnode(2),new intnode(3)), new plusnode(new intnode(1),new intnode(4))); A.print(); Console.WriteLine("\nvalue is "+ A.eval()); newexpressions.test(); // see code below } // main } //// And now for a whole new class of expressions, without changing anything // above. This is the "unary minus" operation, such as in -4: class uminusnode : expr // unary - expression { public expr left; // unary subextression (no right) public uminusnode(expr s) { left = s; } public int eval() { return left.eval() * -1; } public void print() { Console.Write("-"); left.print(); } } // uminusnode // This object oriented organization allows us to modularly extend the // design with new classes that implement the interface without having to // edit the original code. It's completely modular. However, what if we // want to have more than just the eval and print functions for these trees? // How can we modularly extend the program (without editing it) but still // reuse the existing code? How do we avoid starting froms scratch? Let's try // Want to add new method to find depth (height) of trees: interface expr2 : expr { int depth(); } // need to extend each existing class class intnode2 : intnode, expr2 { public intnode2(int v) : base(v) {} public int depth() { return 1; } } class plusnode2 : plusnode, expr2 { public plusnode2(expr2 l, expr2 r): base(l,r) {} public int depth() { return Math.Max(((expr2)left).depth(), ((expr2)right).depth())+1; } } // do same with timesnode, etc... /* This compiles, but will only work if you use expr2, intnode2, plusnode2, etc. throughout your program, which means it's incompatible with code that's referring to the original interface and classes: you will have to EDIT all of it to use your new interface and classes. For example, if I want to find the depth of the expression tree A in main, I would have to recreate it from scratch. I would have to recreate all trees. */ /* Extensions: C# has a deceptive feature called "extension methods" that appears to allow to you add new functions to existing classes (without defining a subclass). But this feature *does not allow dynamic dispatch* on the new function, and is therefore useless with respect to this oop design. */ static class newexpressions // holder class for extensions, must be static { public static int depth(this expr e) { return 0; } // dummy holder //public abstract int depth(this expr e); // compiler errors // extensions must be static, can't override: this is a hint public static int depth(this intnode e) { return 1; } public static int depth(this operatornode e) // inherited by other nodes? {return Math.Max(e.left.depth(), e.right.depth())+1; } public static int dept(this uminusnode e) { return e.left.depth()+1; } // Everything compiles so far, so there's hope! public static void test() { expr A = new plusnode(new intnode(2),new uminusnode(new intnode(3))); Console.WriteLine( A.depth() ); // prints 0!! called expr.depth() } // The test function shows that when A.depth() is called, the compiler // chose to call the version of depth based on the STATIC type of A, which // is expr. Dynamic dispatch did NOT take place. // The only difference between defining `static int depth(expr e)` // and `static int depth(this expr e)`, with `this`, is that you would // call the former with depth(A) and the latter with A.depth(). It // only gives you a different style of SYNTAX. That could be useful, // because it allows you to call a series of functions on an object // using a.f().g().h() instead of h(g(f(a))). But beyond that it adds // nothing to the language. }//static class // One more thing, in order to even get the newexpressions class to compile // I also had to change the left,right variables in operatornode and // uminusnode from protected to public. 'protected' isn't as bad as 'private', // because you can define a helper subclass that re-export protected memebers // as public, but you're not defining a subclass.