An effective way to represent Mathematical expressions is using the binary trees

Subject:Computer SciencePrice:4.86 Bought7

Share With

An effective way to represent Mathematical expressions is using the binary trees. The following algorithm can be employed to generate an expression tree from a given postfix expression

1. Scan the postfix expression from left to right.

2. Make a node Curr

3. Get a symbol E from the expression.

4. If the symbol is an operand

Set this operand as data member of the node Curr

Push the node on the stack 

 

5. If the symbol is an operator

T2 = Pop()

T1 = Pop()

Attach T1 to the left and T2 to the right of Curr

Set the operator as data member of the node Curr

Push Curr (with child nodes attached) onto the stack

 

6. Repeat Steps 1-5 till end of expression

7. Pop the (only remaining) node from the stack which is a pointer to the root of the expression tree

 

Consider the following class to model a node of the tree

class TNode

{

public:

char data;

TNode * left;

TNode * right;

};

Implement the function TNode * constructTree(string postfix) to convert a given postfix expression into an expression tree. Use the stack class in the STL library and make a Stack as follows.

stack <TNode *> s;

 

Call the function constructTree() with the postfix expression: "ab+ef*g*-" Traverse the produced tree in postorder to verify its correctness. You should get back the input string.