Expression trees, Data Structure & Algorithms

What are the expression trees? Represent the below written expression using a tree.

Give a relevant comment on the result that you get when this tree is traversed in Preorder, Inorder and postorder. (a-b) / ((c*d)+e)

The leaves of an expression tree are operands, for instance constants or variable names, and the other nodes include operators. This particular tree happens to be a binary tree, because all of the operations are binary, and although this is the easiest case, it is probable for nodes to have more than two children. It can also be possible for a node to have only one child, as is the case with the unary minus operator. We can evaluate the expression tree, T, by applying the operator at the root of it  to the values obtained by recursively evaluating the left and right subtrees.

The expression tree obtained for the expression: (a - b ) / ( ( c * d ) + e))

1269_expression_tree.png

The traversal of the above drawn expression tree gives the following result:-

Preorder:- ( / - a b + * c d e)

This expression is the same as the "prefix notation" of the original expression.

Inorder:- ( a - b) / ((c * d) + e )

Thus the inorder traversal gives us the actual expression.

Postorder:- ( a b - c d * e + / )

Thus the postorder traversal of this gives us the "posfix notation" or we can say the "Reverse Polish notation" of the original expression.

Posted Date: 7/9/2012 10:28:12 PM | Location : United States







Related Discussions:- Expression trees, Assignment Help, Ask Question on Expression trees, Get Answer, Expert's Help, Expression trees Discussions

Write discussion on Expression trees
Your posts are moderated
Related Questions
In a circular linked list There is no beginning and no end.

what is tree

What do you mean by hashing? Hashing gives the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing func

Assume a complete binary tree T with n nodes where each node has an item (value). Label the nodes of the complete binary tree T from top to bottom & from left to right 0, 1, ..., n

In any singly linked list, each of the elements contains a pointer to the next element. We have illustrated this before. In single linked list, traversing is probable only in one d

Write an algorithm to calculate a postfix expression.  Execute your algorithm using the given postfix expression as your input : a b + c d +*f ↑ . T o evaluate a postfix expr

In this unit, we will describe a data structure called Graph. Actually, graph is a general tree along no parent-child relationship. In computer science, Graphs have several applica


Generally, Computational complexity of algorithms are referred to through space complexity (space needed for running program) and time complexity (time needed for running the progr

The two famous methods for traversing are:- a) Depth first traversal b) Breadth first