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))


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
the voltage wave forms are applied at the inputs of an EX-OR gate. determine the output wave form

Enumerate the Types in Ruby Ruby is a pure object-oriented language, meaning that all types in Ruby are classes, and each value in a Ruby program is an instance of a class. Thi

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Question

Define the term array. An array is a way to reference a series of memory locations using the same name. Each memory location is represented by an array element. An  array eleme

Program segment for deletion of any element from the queue delete() { int delvalue = 0; if (front == NULL) printf("Queue Empty"); { delvalue = front->value;

Ans: A procedure to reverse the singly linked list: reverse(struct node **st) { struct node *p, *q, *r; p = *st; q = NULL; while(p != NULL) { r =q;

Q. Let X = (X1, X2, X3,....Xn) and Y= (Y1, Y2, Y3,....Xm) be the two linked lists respectively. Write down an algorithm to merge the lists together to get the linked list Z such th

The Ruby Programming Language Although data structures and algorithms we study aren't tied to any program or programming language, we need to write particular programs in speci

Let G=(V,E) be a graph for which all nodes have degree 5 and where G is 5-edge is connected. a) Show that the vector x which is indexed by the edges E and for which xe = 1/5 for

Q. Write down any four applications or implementation of the stack.                                     Ans. (i)       The Conversion of infix to postfix form (ii)