5.9 Expression Trees

 < Day Day Up > 



5.9 Expression Trees

As was pointed out earlier, interfaces can also be used in algorithms to abstract out the objects acted on when executing an algorithm. For example, consider the use of an interface in representing an expression tree. An expression tree is a binary tree representing an arithmetic expression. It has two types of nodes. Internal nodes are operators, such as "+" or "-." Leaf nodes are operands, in this case constant. These trees can be used to represent arithmetic equations. Exhibits 12 and 13 are examples of expression trees. Exhibit 12 represents the expression "((5 - 3) + 1)" and Exhibit 13 represents the expression "(5 - (3 + 1))." As the fully parenthesized expressions infer, these expression trees are different and will yield different results. The problem with this tree is that the internal operator nodes do not know what type of node its left or right children are. The children of an operator node could be either another operator node or an operand node. This makes building and evaluating the tree difficult.

Exhibit 12: Tree Map #1

start example

click to expand

end example

Exhibit 13: Tree Map #2

start example

end example

However, if each operator node in the expression tree could simply call an evaluate method on its children's nodes, which would return the result of the operation to its parent, it would not matter if the node was an operator or an operand node. The equation could be calculated by simply calling evaluate on the root node of the tree, and the answer would simply be returned as each node is evaluated. The problem is that obviously the two types of nodes for this tree are very different. The operand nodes store a constant value and have no children, whereas the operator nodes have an operator and left and right children, the children being either operator or operand nodes. Somehow the operator node needs to reference its children in such a way that whether they are operator nodes or operand nodes does not matter.

The solution here is to realize that all the evaluate method in the operator node cares about is that the left and right children are evaluated and an answer is returned; therefore, an interface can be created that simply specifies that a node is something that can be evaluated via a call to its evaluate method, and the OperatorNode and OperandNode classes can implement this interface. This Node interface is shown in Exhibit 14 (Program5.5). The operator class is now defined so that its left and right children are nodes; however, it really does not matter what type of node the children are. The expression tree can then be built of nodes, which are either OperatorNode or OperandNode type, and when the evaluate method on the root is called the expression tree is processed. The value returned from the root is the value calculated by the arithmetic expression represented in the tree.

Exhibit 14: Program5.5: Expression Tree

start example

 interface Node {   public void printTree();   public float evaluate(); } /**  *  An OperatorNode is a tree node that stores an operator. An  *  operator needs both left and right children (all operators  *  are binary). When printing or evaluating the node, the  *  printTree or evaluate methods are called on the children,  *  and the result is handed back to the calling method.  */ class OperatorNode implements Node {   char operator;   Node left, right;   public OperatorNode(char operator, Node left, Node right) {     this.operator = operator;     this.left = left;     this.right = right;   }   public void printTree() {     System.out.print("(");     left.printTree();     System.out.print(""+ operator);     right.printTree();     System.out.print(")");   }   public float evaluate() {     if (operator = = '+')       return left.evaluate() + right.evaluate();     else if (operator = = '-')       return left.evaluate() - right.evaluate();     else       return 0;//Invalid condition     }   }   /**    *  An OperandNode is a leaf node that stores a value. It has    *  no children, thus the printTree and evaluate methods    *  simply return or print the value currently stored in the    *  node.    */   class OperandNode implements Node {     float value;     public OperandNode(float value) {       this.value = value;     }     public void printTree() {       System.out.print(""+ value);     }     public float evaluate() {       return value;     }   }   /**    *  ExpressTree is the driver program that shows how the    *  expression tree program works. It builds trees of operator    *  and operand nodes and then prints and evaluates those    *  trees.    */   public class ExpressionTree {     public static void main(String args[]) {       Node root;     //((5 - 3)+1)     root = new OperatorNode('+',            new OperatorNode('-',            new OperandNode(5), new OperandNode(3)),            new OperandNode(1));     root.printTree();     System.out.println("= "+ root.evaluate());     //(5 - (3+1))     root = new OperatorNode('-',            new OperandNode(5),            new OperatorNode('+',            new OperandNode(3), new OperandNode(1)));     root.printTree();     System.out.println("= "+ root.evaluate());   } } 

end example



 < Day Day Up > 



Creating Components. Object Oriented, Concurrent, and Distributed Computing in Java
The .NET Developers Guide to Directory Services Programming
ISBN: 849314992
EAN: 2147483647
Year: 2003
Pages: 162

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net