Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 3 M

Year: Dec 2013

Compilers need to generate assembly code in which one operation is executed at a time and the result is retained for other operations.

Therefore, all expression have to be broken down unambiguously into separate operations and put into their proper order.

Hence, expression tree is useful which imposes an order on the execution of operations.

The arithmetic expressions represented as binary trees are known as expression trees.

The root node is operator and the left and right children are operands.

Common operators are (negation) unary and (addition, subtraction, multiplication, and division) binary.

Parentheses do not appear in expresion trees, but their intent remains intact in tree representation.

This restricted structure simplifies the programmatic processing of Expression trees.

Example:

Consider the following expression (3+4)*8. The following expression can be represented by expression tree as follows:

Figure 1: Expression Tree