Binary expression tree

related to software enginering

1. Data Structures Presentation By: Amna Iqbal Amna Muzzafar Asma Iqbal Faiza Zahid Maryam Tariq Sumaira Shabana kausar Shamsa Tahseen Fatima Zeerak

2. 2 An application of binary trees Binary Expression Trees

3. 3 A special kind of binary tree in which: The leaves of a binary expression tree are operands, such as constants or variable names , and the other nodes contain operators Each leaf node contains a single operand Each nonleaf node contains a single binary operator 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 . A Binary Expression Tree is . . .

4. 4 A Binary Expression Tree What value does it have? ( 4 + 2 ) * 3 = 18 ‘*’ ‘+’ ‘4’ ‘3’ ‘2’

5. 5 A Four-Level Binary Expression ‘*’ ‘-’ ‘8’ ‘5’ ‘/’ ‘+’ ‘4’ ‘3’ ‘2’

6. Expression Tree Examples Inorder Traversal Result Expression Tree Expression a + 3 (a+3) 3+4*5-9+6 3+(4*5-(9+6)) log x log(x) n ! n! + 3 a + - 3 * 5 4 + 6 9 log x ! n

7. Infix Expressions When you write an arithmetic expression such as B * C, the form of the expression provides you with information so that you can interpret it correctly. In this case we know that the variable B is being multiplied by the variable C since the multiplication operator * appears between them in the expression This type of notation is referred to as  infix  since the operator is  in between  the two operands that it is working on. 7

8. Prefix Expressions Prefix expression notation requires that all operators precede the two operands that they work on. A + B * C would be written as +A*BC in prefix. The multiplication operator comes immediately before the operands B and C, denoting that * has precedence over +. The addition operator then appears before the A and the result of the multiplication. 8

9. Postfix Expressions Postfix requires that its operators come after the corresponding operands. A + B * C would be written as ABC*+ in postfix. The multiplication operator appears immediately after the B and the C, denoting that * has precedence, with + coming after. 9

10. Examples of Infix, Prefix, and Postfix 10 Infix Expression Prefix Expression Postfix Expression A + B + A B A B + A + B * C + A * B C A B C * +

11. 11 Easy to generate the infix, prefix, postfix expressions (how?) Infix: ( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) ) Prefix: * - 8 5 / + 4 2 3 Postfix: 8 5 - 4 2 + 3 / * ‘*’ ‘-’ ‘8’ ‘5’ ‘/’ ‘+’ ‘4’ ‘3’ ‘2’

12. Infix to Postfix conversion (manual) An Infix to Postfix manual conversion algorithm is: 1. Completely parenthesize the infix expression according to order of priority you want. 2. Move each operator to its corresponding right parenthesis. 3. Remove all parentheses. Examples: 3 + 4 * 5 ( 3 + (4 * 5) ) 3 4 5 * + a / b ^ c – d * e – a * c ^ 3 ^ 4 a b c ^ / d e * a c 3 4 ^ ^ * - - ((a / (b ^ c)) – ((d * e) – (a * (c ^ (3 ^ 4) ) ) ) ) Using normal mathematical operator precedence Not using normal mathematical operator precedence

13. 13 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). Each operator has a  precedence  level. Operators of higher precedence are used before operators of lower 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.

14. Tree Traversal A tree traversal is a specific order in which to trace the nodes of a tree. 14

15. Types Of Tree Traversal There are 3 common types of tree traversals. I n-order. 2. Pr e-order. 3. Post-order . 15

16. 16 Inorder Traversal: In-order: left, root, right (A + H) / (M - Y) ‘/’ ‘+’ ‘A’ ‘H’ ‘-’ ‘M’ ‘Y’ tree Print left subtree first Print right subtree last Print second

17. 17 Preorder Traversal: Pre-order: root, left, right / + A H - M Y ‘/’ ‘+’ ‘A’ ‘H’ ‘-’ ‘M’ ‘Y’ tree Print left subtree second Print right subtree last Print first

18. 18 ‘/’ ‘+’ ‘A’ ‘H’ ‘-’ ‘M’ ‘Y’ tree Print left subtree first Print right subtree second Print last Postorder Traversal: Post-order: left, right, root A H + M Y - /

19. 19 Building a Binary Expression Tree from an expression in prefix notation Insert new nodes, each time moving to the left until an operand has been inserted. Backtrack to the last operator, and put the next node to its right. Continue in the same pattern.

20. Algorithm for Expression tree

21. Algorithm for Expression tree 1 Scan expression from left to right until end of string 2 If (symbol = operand) P= new node P.data = symbol Push(P) Else Ptr1= Pop() Ptr2= Pop() P= new node P.data = symbol P.Lchild = Ptr2 P.Rchild =Ptr1 Push(P) 3 Exit

22. How to scan an expression 1. While there are still tokens to be read in, 1.1 Get the next token. 1.2 If the token is: 1.2.1 A number: push it onto the value stack. 1.2.2 A variable: get its value, and push onto the value stack. 1.2.3 A left parenthesis: push it onto the operator stack. 1.2.4 A right parenthesis: 1 While the thing on top of the operator stack is not a left parenthesis, 1 Pop the operator from the operator stack. 2 Pop the value stack twice, getting two operands. 3 Apply the operator to the operands, in the correct order. 4 Push the result onto the value stack. 2 Pop the left parenthesis from the operator stack, and discard it .

23. How to scan an expression 1.2.5 An operator (call it thisOp ): 1 While the operator stack is not empty, and the top thing on the operator stack has the same or greater precedence as thisOp , 1 Pop the operator from the operator stack. 2 Pop the value stack twice, getting two operands. 3 Apply the operator to the operands, in the correct order. 4 Push the result onto the value stack. 2 Push thisOp onto the operator stack.

24. How to scan an expression 2. While the operator stack is not empty, 1 Pop the operator from the operator stack. 2 Pop the value stack twice, getting two operands. 3 Apply the operator to the operands, in the correct order. 4 Push the result onto the value stack. 3. At this point the operator stack should be empty, and the value stack should have only one value in it, which is the final result