/* 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 exptree3b { 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()); // testing "extension methods below" Console.WriteLine("size is "+ A.size()); } // 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 { 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? //// in trying to add features modularly, I must resist the urge to just // edit the code, but I can't 'cause the boss will kill me. But // in the end I still had to make one change: protected to public. // I could do this with a helper class - but too hard. //// Trying new C# feature: "extension methods" static class exprextensions { //public int size(this expr x); // wont' compile public static int size(this expr x) // static dispatch on x { return 0; } // default that hopefully can be overridden? /* public static int size(this expr x) // static dispatch on x { if (x is intnode) return 1; // this is not OOP! else { operatornode xo = (operatornode)x; return xo.left.size() + xo.right.size() + 1; } } // why oop? */ public static int size(this intnode n) { return 1; } public static int size(this operatornode n) { return 1 + n.left.size() + n.right.size(); } public static int size(operatornode n) { return 1+size(n.left)+size(n.right); } // f(n) n.f() }//exprextensions // clearly, extension methods cannot use dynamic dispatch, and thus // don't give us what we want.