[ Data Structures with Java ] Section 17.1 : Expression Trees

Preface : 
A compiler uses a binary tree to represent an arithmetic expression. The nodes of the tree, called an expression tree, are binary operators and operands. We will now develop an algorithm that shows you how to take an arithmetic expression in postfix notation and create the expression tree. You can refer back to Chapter 14 in which we introduced infix and postfix notation for an arithmetic expression. These formats specify the position of a binary operator and its operands. In postfix notation, the binary operator comes after its operands, and in infix notation, the operator appears between its operands. A third notation, called prefix notation, places a binary operator before its operands. The expressions in below table include each of the formats : 
 

Assume an arithmetic expression involves the binary operators addition (+), subtraction (-), multiplication (*) and division (/). In the expression tree, each operator has two children that are either operands or subexpressions. A binary expression tree consists of : 

* leaf nodes with contains a single operand
* nonleaf nodes which contains a binary operator
* the left and the right subtrees of an operator, describing a subexpression, which in evaluated and used as one of the operands for the operator.

The trees in below figure describe the expression in upper table : 
 

The preorder and postorder traversals of a binary expression tree produce the prefix and postfix notation for the expression. An inorder traversal generates the infix form of the expression, assuming that parentheses are not needed to determine the order of evaluation. For instance, in upper figure (c), the following are different traversals of the expression : a + b * c / d - e 

Preorder (Prefix) : - + a / * b c d e
Inorder (Infix) : a + b * c / d - e
Postorder (Postfix) : a b c * d / + e -

Building a Binary Expression Tree : 
To build an expression tree, we need to develop an iterative algorithm that takes a string containing an expression in postfix form. An operand is a single character such as 'a' or 'b'. Our algorithm follows the steps of the postfix evaluation algorithm in Section 14.4. A stack holds the operands, which in this case are trees. More specifically, the stack holds TNode references that are the root of subtree operands. In the postfix evaluation algorithm, whenever we located an operator, we popped its two operands from the stack and computed the result. In this algorithm, when we locate an operator, we construct a subtree and insert its root reference onto the stack. The following is a description of the action taken when we encounter an operand or an operator in the input string : 

* If the token is an operand, we use its value to create a leaf node whose left and right subtrees are null. The leaf node is pushed onto a stack of TNode references.
* If the token is an operator, we create a new node with the operator as its value. Because the operator is binary, it must have two children in the tree. The children hold the operands for the operator. A child may be a single operand (leaf node) or a subexpression represented by a subtree with an operator as the root. The child nodes are on the stack from a previous step. Pop the two child nodes from the stack and attach them to the new node. The first child popped from the stack becomes the right subtree of the new node and the second child popped from the stack becomes the left subtree.

The method buildExpTree() implements the algorithm. The following steps illustrate the action of the method for the expression a+b*c in postfix form. We represent the stack horizontally to simply the view of the elements. Remember, each element is a subtree specified by its root : 
Considering postfix expression : a b c * + 
Step1: Recognize 'a' as an operand. Construct a leaf node containing the Character value 'a' and push its reference onto the stack s : 
 
Step2-3: Recognize 'b' and 'c' as operands, construct leaf nodes, and push their references onto the stack. 
 
Step 4: Recognize '*' as an operator. Create a new node with '*' as its value. Then pop two subtrees (node 'c' and node 'b') from the stack. These are the right and left node respectively. Attach the subtrees and push the new subtree (root '*') on the stack. 
 
Step 5: Recognize '+' as an operator. Create a new node with '+' as its value. Pop its two operands from the stack, attach them to the node, and push the new subtree (root '+') on the stack. 
 
Step 6: We have reached the end of the expression. The single item on the stack is the root of the expression tree. 

The method buildExpTree() applies this algorithm to construct the expression tree for a correctly formed postfix expression. The method performs no error checking. It assumes that an operand is a single character and that the available operators are +, - , * and /. In addition, the expression can contain the whitespace characters blank or tab. Below is the implementation : 

- ExpressionTree.java : Implementation on Method buildExpTree()

view plaincopy to clipboardprint?

1. package DSwJ.S17;  
2.   
3. import DSwJ.S14.ALStack;  
4. import DSwJ.S16.BinaryTree;  
5. import DSwJ.S16.TNode;  
6.   
7. public class ExpressionTree {  
8.     public static TNode buildExpTree(String postfixExp) {  
9.         ALStack> s = new ALStack>();  
10.         postfixExp = postfixExp.trim();  
11.         char token;  
12.         int i=0, n=postfixExp.length();  
13.         while(i
14.             token = postfixExp.charAt(i);  
15.             if(token==' ' || token == '\t') {  
16.                 i++;  
17.                 continue;  
18.             }  
19.             if(token=='+'||token=='-'||token=='*'||token=='/') {  
20.                 /*Operator*/  
21.                 TNode right = s.pop();  
22.                 TNode left = s.pop();  
23.                 TNode root = new TNode(token, left, right);  
24.                 s.push(root);  
25.             } else {  
26.                 /*Operand*/  
27.                 TNode leafNode = new TNode(token);  
28.                 s.push(leafNode);  
29.             }  
30.             i++;  
31.         }  
32.           
33.         if(s.isEmpty())   
34.             return null;  
35.         else   
36.             return s.pop();  
37.     }  
38.       
39.     public static void main(String args[]) {  
40.         String input = "abc*d-e/*";  
41.         System.out.println("Input: "+input);  
42.         TNode expTree = buildExpTree(input);  
43.         System.out.println("Preorder scan: "+BinaryTree.preorderDisplay(expTree));  
44.         System.out.println("Postorder scan: "+BinaryTree.postorderDisplay(expTree));  
45.         System.out.println("Inorder scan: "+BinaryTree.inorderDisplay(expTree));  
46.     }  
47. }  

Run :
Input: abc*d-e/*
Preorder scan: * a / - * b c d e
Postorder scan: a b c * d - e / * 
Inorder scan: a * b * c - d / e

Actually, it will build a binary tree as below :