/*****************************************************************************/ /* */ /* Prefix Enumeration of an Expression Tree: Graphical Version */ /* */ /* January 1999, Toshimi Minoura */ /* November 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 subexpression represented // by the subtree under the non-leaf node is computed. // This program generates the prefix representation for an agebraic // expression represented by a systax tree graphically. // It also produces a textual printout in pre-, in-, and post-fix. import java.awt.*; import java.awt.event.*; class PrefixG extends StepTestCanvas { static final Color OutlineColor = new Color( 100, 0, 0 ); // for node outline 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 String value; // value associated with this node Node leftChild; // left subexpression Node rightChild; // right subexpression int xLoc; // x location of center of this Node int yLoc; // y location of center of this Node boolean visited; // this node already visited if true // Constructor for a leaf node. Node( String name, int val, int x, int y ) { 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 xLoc = x; yLoc = y; System.out.println( "leaf node " + name + " created, value = " + value ); } // Constructor for a branch node. Node( String name, char opCode, Node leftNode, Node rightNode, int x, int y ) { this.name = name; // set name operator = new Operator( opCode ); // create operator for given symbol value = null; // no initial value leftChild = leftNode; // set left subexpression rightChild = rightNode; // set right subexpression xLoc = x; yLoc = y; System.out.println( "operator node " + name + " created for " + leftChild.name +" " + operator + " " + rightChild.name ); } // Enumerate subexpression (prefix). public String toPrefix( PrefixG canvas ) { if( operator != null ) // Non-leaf, compose subexpression in PRE. value = operator.symbol + " " + leftChild.toPrefix( canvas ) + " " + rightChild.toPrefix( canvas ); currentNode = this; visited = true; canvas.repaintStep( "Node " + name + " visited: Subexpression in PRE = " + value + "." ); return value; } // Enumerate subexpression (postfix). public String toPostfix( PrefixG canvas ) { if( operator != null ) // Non-leaf, compose subexpression in POS. return "" + leftChild.toPostfix( canvas ) + " " + rightChild.toPostfix( canvas ) + " " + operator.symbol; else // Leaf node, return value. return value; // currentNode = this; // visited = true; // canvas.repaintStep( "Node " + name + " visited: Subexpression in POS = " + value + "." ); // return value; } // convert an expression tree to String public String toString() { // Leaf node? if( operator == null ) // Return String for subexpression. return "" + value; else return "(" + leftChild + operator + rightChild + ")"; } public void draw( Graphics g ) { int nodeWidth = 40; int nodeHeight = 30; // 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( value, xLoc - 3, yLoc + 5 ); else g.drawString( "" + operator, xLoc - 3, yLoc + 5 ); // Operator node with value. if( operator != null && value != null ) { g.setColor( DarkLetter ); g.drawString( value, xLoc - 5, yLoc - nodeHeight / 2 - 5 ); } // Is this non-leaf node? if( operator != null ) { leftChild.draw( g ); rightChild.draw( g ); } } } private Node root = null; private static Node currentNode = null; // node currently being visited static final int xLoc = 100; // x location of left side of tree public void initialize() { System.out.println( "PrefixG.initialize() entered." ); Node node1 = new Node( "n1", 1, 250, 200 ); // leaf with value 1 Node node2 = new Node( "n2", 2, 100, 200 ); // leaf with value 2 Node node3 = new Node( "n3", 3, 300, 200 ); // leaf with value 3 Node node4 = new Node( "n4", 4, 350, 200 ); // leaf with value 4 Node node5 = new Node( "n5", 5, 400, 200 ); // leaf with value 5 Node node6 = new Node( "n6", 6, 50, 200 ); // leaf with value 6 Node node7 = new Node( "n7", 7, 200, 200 ); // leaf with value 7 Node node8 = new Node( "n8", 8, 150, 200 ); // leaf with value 8 Node nodeB = new Node( "nB", '*', node1, node3, 270, 150 ); Node nodeE = new Node( "nE", '*', node4, node5, 360, 150 ); Node nodeA = new Node( "nA", '+', nodeB, nodeE, 300, 100 ); Node nodeC = new Node( "nC", '+', node6, node2, 90, 150 ); Node nodeG = new Node( "nG", '+', node8, node7, 180, 150 ); Node nodeF = new Node( "nF", '*', nodeC, nodeG, 150, 100 ); Node nodeD = new Node( "nD", '+', nodeF, nodeA, 225, 50 ); root = nodeD; // set new root node repaintStep(); } Font f = new Font( "TimesRoman", Font.BOLD, 18 ); public synchronized void paint( Graphics g ) { if( root == null ) { // Root of tree not created yet, initial condition. g.drawString( "Tree is empty.", 150, 80 ); return; } // Set font for letters. g.setFont( f ); root.draw( g ); } // Execute thread. public void runMain() { System.out.println( "runMain() in PrefixG entered" ); initialize(); System.out.println( "Infix enumeration: " + root.toString() + "." ); System.out.println( "Prefix enumeration: " + root.toPrefix( this ) + "." ); System.out.println( "Postfix enumeration: " + root.toPostfix( this ) + "." ); } public static void main( String argv[] ) { new StepTestFrame( "Evaluation of Expression Tree", new PrefixG(), 500, 400 ).show(); } }