/*****************************************************************************/ /* */ /* Evaluating an Expression in Tree Form: Graphical Version */ /* */ /* January 1999, Toshimi Minoura */ /* October 1999, Jacob Lundberg */ /* */ /*****************************************************************************/ // An expression is represented by a tree. // Each node in this tree can store an operator and a value. // For a leaf node, only its value is relevant. // For each non-leaf node, the value for the subexpression represented // by the subtree under the non-leaf node is computed. // Each node calculates its own location in the tree's graphical display. import java.awt.*; import java.awt.event.*; class ExpressTreeG extends StepTestCanvas { // Expected display size. static final int WIDTH = 450; static final int HEIGHT = 300; // For node outline. static final Color OutlineColor = new Color(100, 0, 0); static final Color NodeColor = new Color(0, 100, 0); static final Color FocusColor = new Color(225, 225, 0); static final Color VisitedColor = new Color(0, 0, 200); static final Color DarkLetter = new Color(0, 0, 100); static final Color LightLetter = new Color(255, 255, 255); static final Color LineColor = new Color(100, 0, 0); // Class for operators. class Operator { public char symbol; // +, *, etc. // Constructor for an Operator object. Operator( char x ) { symbol = x; } // Apply this operator to two integers. public int eval( int x, int y ) { if( symbol == '+' ) // this operator is addition return x + y; if( symbol == '*' ) // this operator is multiplication return x * y; return -1; // illegal operator encountered } public String toString() { return "" + symbol; // convert char to String } } class Node { String name; // name of this node, for debugging public Operator operator; // operator represented by this node public int value; // value associated with this node Node leftChild; // left subexpression Node rightChild; // right subexpression boolean visited; // this node already visited if true int rights; // how many right turns to get here? int height; // how many "high" below the top? // Constructor for a leaf node. Node( String name, int val ) { this.name = name; // set name operator = null; value = val; // set value for this leaf node leftChild = null; // no left subexpression rightChild = null; // no right subexpression rights = 0; height = 0; System.out.println( "Leaf node " + name + " created, value = " + value + "." ); } // Constructor for a branch node. Node( String name, char opCode, Node leftNode, Node rightNode ) { this.name = name; // set name operator = new Operator( opCode ); // create operator for given symbol value = -1; // no initial value leftChild = leftNode; // set left subexpression rightChild = rightNode; // set right subexpression rights = 0; height = 0; if( leftChild != null ) leftChild.addStep( 0 ); if( rightChild != null ) rightChild.addStep( 1 ); System.out.println( "Operator node " + name + " created for " + leftChild.name + " " + operator + " " + rightChild.name + "." ); } // Add a step to get here. private void addStep( int count ) { ++height; rights = count; count *= 2; if( leftChild != null ) leftChild.addStep( count ); if( rightChild != null ) rightChild.addStep( ++count ); } // Evaluate subexpression for node. public int eval( ExpressTreeG canvas ) { if ( operator != null ) // is this a leaf node? value = operator.eval( leftChild.eval( canvas ), rightChild.eval( canvas ) ); currentNode = this; visited = true; System.out.println( "Node " + name + " visited: value = " + value + "." ); canvas.repaintStep( "Node " + name + " visited: value = " + value + "." ); return value; } // Count how many nodes deep the tree beneath a node is. public int depth() { if( leftChild == null ) if( rightChild == null ) return 1; else return 1 + rightChild.depth(); else if( rightChild == null ) return 1 + leftChild.depth(); else if( leftChild.depth() >= rightChild.depth() ) return 1 + leftChild.depth(); else return 1 + rightChild.depth(); } // Calculate the xLoc for a node by height (which implies max width). public int xLoc() { return WIDTH / ( ( 1 << ( height ) ) + 1 ) * ( 1 + rights ); } // Calculate the yLoc for a node by depth. public int yLoc() { return HEIGHT / ( root.depth() + 2 ) * ( 1 + height ); } public void draw( Graphics g ) { final int nodeWidth = 40; final int nodeHeight = 30; System.out.println( "Node.draw() called for Node " + name + "." ); // Is this non-leaf node? if ( operator != null ) { g.setColor( LineColor ); // draw lines to children nodes g.drawLine( xLoc(), yLoc(), leftChild.xLoc(), leftChild.yLoc() ); g.drawLine( xLoc(), yLoc(), rightChild.xLoc(), rightChild.yLoc() ); } if ( currentNode == this ) g.setColor( FocusColor ); // color for current Node else if ( visited ) g.setColor( VisitedColor ); // color for visited Node else g.setColor( NodeColor ); // color for non-visited node g.fillOval( xLoc() - nodeWidth / 2, yLoc() - nodeHeight / 2, nodeWidth, nodeHeight ); g.setColor( OutlineColor ); g.drawOval( xLoc() - nodeWidth / 2, yLoc() - nodeHeight / 2, nodeWidth, nodeHeight ); if ( currentNode == this ) g.setColor( DarkLetter ); else g.setColor( LightLetter ); if ( operator == null ) g.drawString( Integer.toString( value ), xLoc() - 3, yLoc() + 5 ); else g.drawString( "" + operator, xLoc() - 3, yLoc() + 5 ); // Operator node with value. if ( operator != null && value != -1 ) { g.setColor( DarkLetter ); g.drawString( Integer.toString( value ), xLoc() - 5, yLoc() - nodeHeight / 2 - 5 ); } // Is this non-leaf node? if ( operator != null ) { leftChild.draw( g ); rightChild.draw( g ); } } // Convert an expression tree to String. public String toString() { if ( operator == null ) // leaf node? return "" + value; // yes, convert int to String and return else // return String for subexpression return "(" + leftChild + operator + rightChild + ")"; } } private Node root = null; private static Node currentNode = null; // node currently being visited public void initialize() { System.out.println( "ExpressTreeG.initialize() entered." ); // Note that you must create a node before you can reference it. Node node1 = new Node( "n1", 1 ); // leaf with value 1 Node node2 = new Node( "n2", 2 ); // leaf with value 2 Node node3 = new Node( "n3", 3 ); // leaf with value 3 Node node4 = new Node( "n4", 4 ); // leaf with value 4 Node node5 = new Node( "n5", 5 ); // leaf with value 5 Node node6 = new Node( "n6", 6 ); // leaf with value 6 Node node7 = new Node( "n7", 7 ); // leaf with value 7 Node node8 = new Node( "n8", 8 ); // leaf with value 8 Node nodeB = new Node( "nB", '*', node1, node3 ); Node nodeE = new Node( "nE", '*', node4, node5 ); Node nodeA = new Node( "nA", '+', nodeB, nodeE ); Node nodeC = new Node( "nC", '+', node6, node2 ); Node nodeG = new Node( "nG", '+', node8, node7 ); Node nodeF = new Node( "nF", '*', nodeC, nodeG ); Node nodeD = new Node( "nD", '+', nodeF, nodeA ); root = nodeD; // set new root node repaintStep(); } Font f = new Font( "TimesRoman", Font.BOLD, 18 ); public synchronized void paint( Graphics g ) { System.out.println( "ExpressTreeG.paint() entered." ); // Root of tree not created yet, initial condition. if (root == null) { g.drawString( "Tree is empty.", 150, 80 ); return; } g.setFont( f ); // set font for letters root.draw( g ); } // Execute thread. public void runMain() { System.out.println( "runMain() in ExpressTreeG entered." ); initialize(); System.out.println( "Evaluation of expression: " + root.toString() + "." ); root.eval( this ); System.out.println( "Evaluation completed, root.value = " + root.value + "." ); } public static void main(String argv[]) { new StepTestFrame( "Evaluation of Expression Tree", new ExpressTreeG(), 500, 400 ).show(); } }