Mumbai University > Computer Engineering > Sem 3 > Data Structures

Marks: 5M

Year: May 2016

1. An arithmetic expression such as (5-x)*y+6/(x + z) is a combination of arithmetic operators (+, -, *, /, etc.), operands (5, x, y, 6, z, etc.), and parentheses to override the precedence of operations.
2. Each expression can be represented by a unique binary tree whose structure is determined by the precedence of operation in the expression. Such a tree is called an expression tree.
3. Algorithm for building expression tree: a. The expression tree for a given expression can be built recursively from the following rules: i. The expression tree for a single operand is a single root node that contains it. ii. If E1 and E2 are expressions represented by expression trees T1 and T2, and if op is an operator, then the expression tree for the expression El op E2 is the tree with the root node containing op and sub-trees T1 and T2. b. An expression has three representations, depending upon which traversal algorithms are used to traverse its tree. The preorder traversal produces the prefix representation, the in-order traversal produces the infix representation, and the post-order traversal produces the postfix representation of the expression. The postfix representation is also called reverse Polish notation or RPN.
4. Example of an expression tree: Here is the expression tree for the expression: (5-x)*y+6/(x + z)