Expression tree

Expression tree

1. Expression tree Nagajothi N 1 M.Sc., IT 1

2. Objectives What is expression tree What are expressions in data structures ? W hat kind of expression tree What type of data structure is tree ? Construction of expression tree Traversal of expression tree Algebraic expression tree Boolean expression tree 2

3. What is expression tree A binary expression tree is a  specific kind of a binary tree used to represent expressions . .. These trees can represent expressions that contain both unary and binary operators Each node of a binary tree, and hence of a binary expression tree, has zero, one, or two children . 3

4. What are expressions in data structures? An expression is  a collection of operators and operands that represents a specific value . operator is a symbol which performs a particular task like arithmetic operation or logical operation or conditional operation etc., Operands are the values on which the operators can perform the task 4

5. Operators Operands 5

6. There are three kinds of expressions An arithmetic expression evaluates to a single arithmetic value .( x, x  2 , xy, or 3xy  2 ,) A character expression evaluates to a single value of type character . A logical or relational expression evaluates to a single logical value( TRUE or FALSE) 6

7. What type of data structure is tree? A tree is  a hierarchical data structure  which can represent relationships between different nodes 7

8. Tree structure 8

9. Construction of expression tree Now For constructing an expression tree we  use a stack . If a character is an operator pop two values from the stack make them its child and push the current node again 9

10. example 10

11. Algebraic expression Algebraic expression trees represent expressions that contain  numbers , variables , and unary and binary operators . Some of the common operators are × ( multiplication ), ÷ ( division ), + ( addition ), − ( subtraction ), ^ ( exponentiation ), and - ( negation ) 11

12.   Boolean expressions Boolean expressions use  true  and  false  as constant values, and the operators include    ( AND ),    ( OR ),    ( NOT ). 12

13. Traversal of expression tree infix expression Postfix expression Prefix expression 13

14. infix expression X + Y .  Operators   are written in-between their operands An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer." 14

15. example 15

16. Postfix expression X Y + Operators are written after their operands. The infix expression given above is equivalent to  A B C + * D / 16

17. example 17

18. Prefix expression + X Y Operators are written before their operands. The expressions given above are equivalent to  / * A + B C D 18

19. example 19

20. Thankyou ! 20