/*****************************************************************************/ /* */ /* Postfix Enumeration of an Expression Tree: Graphical Version */ /* */ /* January 1999, Toshimi Minoura */ /* */ /*****************************************************************************/ // 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 deacha non-leaf node, the subexpression represented // by the subtree under the non-leaf node is computed. // This program generates the postfix representation for an agebraic // expression represented by a systax tree. import java.awt.*; import java.awt.event.*; class PostfixG 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 Operator { // class for operators public char symbol; // +, *, etc. Operator(char x) { symbol = x; } // constructor for an Operator object public int eval(int x, int y) { // apply this operator to two integers 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 Node(String name, int val, int x, int y) { // constructor for a leaf node 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); } 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); } public String toPostfix(PostfixG canvas) { // enumerate subexpression if (operator != null) { // non-leaf, compose subexpression in RPN value = leftChild.toPostfix(canvas) + " " + rightChild.toPostfix(canvas) + " " + operator.symbol; } currentNode = this; visited = true; canvas.repaintStep("Node " + name + " visited: Subexpression in RPN = " + value); return value; } public String toString() { // convert an expression tree to String if (operator == null) { // leaf node? return "" + value; // yes, convert int to String and return } else { // return String for subexpression return "(" + leftChild + operator + rightChild + ")"; } } public void draw(Graphics g) { int nodeWidth = 40; int nodeHeight = 30; // System.out.println("Node.draw() called for Node " + name); if (operator != null) { // is this non-leaf node? 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); } if (operator != null && value != null) { // operator node with value g.setColor(DarkLetter); g.drawString(value, xLoc - 5, yLoc - nodeHeight / 2 - 5); } if (operator != null) { // is this non-leaf node? 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("PostfixG.initialize() entered"); Node node1 = new Node("n1", 1, xLoc + 40, 150); // leaf with value 1 Node node2 = new Node("n2", 2, xLoc + 110, 200); // leaf with value 2 Node node3 = new Node("n3", 3, xLoc + 250, 200); // leaf with value 3 Node node4 = new Node("n4", 4, xLoc + 250, 100); // leaf with value 4 Node node5 = new Node("n5", '*', node2, node3, xLoc + 180, 150); Node node6 = new Node("n6", '+', node1, node5, xLoc + 110, 100); Node node7 = new Node("n7", '+', node6, node4, xLoc + 180, 50); root = node7; // set new root node repaintStep(); } Font f = new Font("TimesRoman", Font.BOLD, 18); public synchronized void paint(Graphics g) { System.out.println("PostfixG.paint() entered"); if (root == null) { // root of tree not created yet, initial condition g.drawString("tree is empty.", 150, 80); return; } g.setFont(f); // set font for letters root.draw(g); } public void runMain() { // execute thread System.out.println("runMain() in PostfixG entered"); initialize(); System.out.println("Expression: " + root.toString()); System.out.println("Postfix enumeration: " + root.toPostfix(this)); } public static void main(String argv[]) { new StepTestFrame("Evaluation of Expression Tree", new PostfixG(), 500, 400).show(); } }