question archive An effective way to represent Mathematical expressions is using the binary trees
Subject:Computer SciencePrice:4.86 Bought7
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.
Purchased 7 times