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
List various problem solving techniques. There are two techniques:- 1.  Top down 2.  Bottom- up

Question 1. Explain the different types of traversal on binary tree 2. Explain the Prim's minimum spanning tree algorithm 3. Differentiate fixed and variable storage allo

Write an algorithm for binary search. Algorithm for Binary Search 1.  if (low> high) 2.  return (-1) 3.  Mid = (low + high)/2 4.  if ( X = = a[mid]) 5.  return (mid); 6.

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem

Program will demonstrate the insertion of an element at desired position /* Inserting an element into contiguous list (Linear Array) at particular position */ /* contiguous_

#What is the pointer

The location of a node in a binary search tree is defined as a string such as LLRRL, which represents the node that you find by starting at the root, and traversing Left, traverse

QUESTION (a) Define a tree and list its properties. (b) By showing all your workings, draw the spanning tree for the following graph based on the Breadth-First-Search algori

Linked list representations contain great advantages of flexibility on the contiguous representation of data structures. However, they contain few disadvantages also. Data structur

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.