Expression Tree

Arithmetic involves creating arithmetic expressions using binary operators. Binary operators are the arithmetic operators that require two operands for evaluation. + (addition),-(subtraction), /(division) and * (multiplication) are binary operators. Any expression made from such operators can be represented using a binary tree called an Expression Tree.

Characteristics

• All the operands in the arithmetic expression will always be created as leaf nodes of the Expression Tree.
• All the binary operators of the arithmetic expression will make the internal nodes of the expression tree
• One binary operator of the expression will make the root node which defines the summarized operation will be the root node.

Construction of an Expression tree by observation

The expression tree can be constructed by observing the given arithmetic expression. You always begin with identifying the sub-expressions of the expression. The sub-expressions are usually enclosed in parenthesis. The pair of operands that are associated with one binary operator are also termed as sub expressions. 

Small binary trees are made for sub-expressions. They are then combined depending upon the parenthesis enclosure or operator precedence to make composite sub-expressions.

In the expression a*(b-c)+(d/e), (b-c), (d/e) and a*(b-c) are sub-expressions.  In the expression a*(b-c)+(d/e) these sub-expressions are first converted into expression trees. These expression trees are then combined to make the complete expression tree.

 Consider the following example

Construction by using Stacks

If you are not sure to create an it by observation, you can follow the algorithm using two stack for storing operators and tree nodes. Stack OPERATORS  is used to store opening parentheses. Stack NODES is used to store the nodes that for the Expression Tree. Q is the infix expression given as input.

Every opening parenthesis and operator in Q is pushed on the OPERATORS  stack. Every operand in Q is pushed into NODES stack. When a closing parenthesis is encountered, two nodes are popped from the NODES Stack. The topmost popped node is stored as right child using RIGHT pointer. The second topmost popped node is stored as left child using LEFT pointer. 

From the OPERATORS Stack the topmost operator is popped and a node PARENT is made from it. This PARENT node is updated with LEFT and RIGHT nodes as its left and right child nodes. PARENT pointer is pushed into the NODES Stack. From the OPERATORS Stack the topmost “(” is removed since it matches the “)” in the Q expression.

This process is repeated till the OPERATORS stack becomes empty. The last value present in the NODES stack is the node representing the final Tree. This is popped and returned as ROOT node of the created Expression Tree.

Algorithm CREATE_EXP_TREE(Q, ROOT)
1. Push a “(“ on stack and append “)” at end of the Q
2. Scan the expression Q from left to right  and for each symbol repeat steps 3,4,5 and          6 while stack OPERATORS  is not empty
3. If an “(“ is encountered push it into OPERATORS
4. If an operand is encountered push it in NODES
5. If an operator is encountered   push it in OPERTORS
6. If “)” is encountered 
       Repeat Steps a, b, c and d until "(" is encountered in stack OPERTORS 
        a. Pop operator from OPERATORS and make it a PARENT node.
        b. Pop two nodes from NODES. The topmost is stored as RIGHT and the second      popped is stored as LEFT
       c. Update left and right pointers of PARENT node with LEFT and RIGHT respectively 
       d. Push PARENT in NODES
       e. Remove  “(” from the OPERATOR
7. Pop last available element in stack store in ROOT.
8. Exit

Example

Convert the expression Q=(a + b*c)/d

Initial Step- append “)” to Q – (a+b*c)/d)

Symbol	Stack- Operators	Stack- Nodes	Partial Expression Tree
	(
(	((
a	((	a
+	((+	a
b	((+	ab
*	((+*	ab
c	((+*	abc
)	((+	*
	(	+
/	(/	+
d	(/	+d
)		/

All the symbols from Q are scanned and the last symbol in the Nodes stack is the solution of given infix expression

admin