1.4 expression tree

Data Structure-expression tree

1. Expression Trees

2. Algorithm for evaluating postfix
expressions
Start scanning the postfix expressions from left to right
If operand is encountered then push it on to the stack
If an operator is encountered, pop last two operands from the
stack, apply the operator on the operands and then push the
resultant value on to the stack
Finally the stack must contain the single value which is the result

3. Contd…
Converting infix to postfix and then evaluating the postfix
expression is not useful
It could be useful if we evaluate the postfix expression while it is
being constructed
Using two stacks
Operand stack and
Operator stack will be useful
Infix to postfix- operand stack
Postfix evaluation- operator stack

4. Algorithm for evaluating the infix
expression
Start scanning the infix expression from left to right
If an operand is encountered, push it on to the operand stack
If an operator is encountered, do the following
Pop until operator stack top has higher or equal precedence than
current operator, before pushing the current operator on to the stack
While popping an operator, pop last two operands from the operand
stack, apply the operator on the operands and then push the result on
to the operand stack
Finally the operand stack has the single value which is the result.

5. Algorithm for constructing a
binary expression tree
Start scanning the infix expression from left to right
If an operand is encountered, create a binary node and push its
pointer onto the operand stack
If an operator is encountered, create a binary node and do the
following
Pop until operator stack top has higher or equal precedence than
current operator, before pushing the pointer on to the operand stack
While popping an operator pointer, pop last two pointers from the
operand stack, and make the pointers left and right child and then
operator pointer on to the operand stack
Finally top of the operand stack has the root of the expression
tree.

6. Note:
The only differences between last two algorithms are the
following.
instead of just pushing the operator / operand, we create
a binarynode and we push the pointers
instead of applying the operator on two operands, we
make the left and right child
instead of pushing the resultant value into the stack, we
push the operator node pointer into the operand stack.

7. A Binary Expression Tree is . . .
A special kind of binary tree in which:
1. Each leaf node contains a single operand
2. Each nonleaf node contains a single binary
operator
3. The left and right subtrees of an operator
node represent subexpressions that must be
evaluated before applying the operator at the
root of the subtree.
7

8. A Four-Level Binary Expression

8
‘*’
‘-’
‘8’ ‘5’
‘/’
‘+’
‘4’
‘3’
‘2’

9. Levels Indicate Precedence
The levels of the nodes in the tree indicate
their relative precedence of evaluation (we
do not need parentheses to indicate precedence).
Operations at higher levels of the tree are
evaluated later than those below them.
The operation at the root is always the last
operation performed.
9

10. A Binary Expression Tree

10
What value does it have?
( 4 + 2 ) * 3 = 18
‘*’
‘+’
‘4’
‘3’
‘2’

11. Easy to generate the infix, prefix, postfix
expressions (how?)

11
Infix: ( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) )
Prefix: * - 8 5 / + 4 2 3
Postfix: 8 5 - 4 2 + 3 / *
‘*’
‘-’
‘8’ ‘5’
‘/’
‘+’
‘4’
‘3’
‘2’

12. Do by yourself
Evaluate Following Postfix Expression:
(1) 3 * 2 + 4 * (A + B)
(2) A * (B + C) * D
(3) A * (B+C–D/E)/F
(4) A * B + (C – D/E)
(5) (a + b – c) * (e / f) – ( g – h/i)
(6) 1*1*8-5*(6-4*3-5*(7-(2*5)))
(7) (300+23)*(43-21)/(84+7)
(8) (4+8)*(6-5)/((3-2)*(2+2))
(9) 6-6/7-4*5/7-1/4*4
(10) 5*4-2+3-7+2/2*1/8/4

13. How many squares can you create in this figure by connecting any 4 dots (the
corners of a square must lie upon a grid dot?
TRIANGLES:
How many triangles are located in the image below?

14. There are 11 squares total; 5 small, 4 medium, and 2 large.
27 triangles. There are 16 one-cell
triangles, 7 four-cell triangles, 3 nine-
cell triangles, and 1 sixteen-cell
triangle.

15. GUIDED READING

16. MIND MAP

17. ASSESSMENT
1. The postfix expression for the infix expression A +
B*(C+D)/F + D*E is
A.AB+CD+*F/D+E*
B.ABCD+*F/DE*++
C.A*B+CD/F*DE++
D.A+*BCD/F*DE++

18. Contd..
2. The leaf nodes of binary expression tree contains
A.both operators and operands
B.only operators
C.only operands
D.neither operators nor operands

19. Contd..
3. The root of the expression tree of (a/b*c)+(5-4+(d*e+f)*g) is
A.+
B.*
C.-
D./

20. Contd..
4. Which one of the following statement is correct.
A.‘(‘ has highest precedence in the expression and lowest
precedence when present in the stack
B.‘)‘ has highest precedence in the expression and lowest
precedence when present in the stack
C.‘(‘ has lowest precedence in the expression and lowest
precedence when present in the stack
D.‘(‘ has highest precedence in the expression and highest
precedence when present in the stack

21. Contd..
5. The traversal technique which output the postfix notation of
binary expression tree is
A.pre-order traversal
B.converse post-order traversal
C.post order traversal
D.converse pre-order traversal