An effective way to represent Mathematical expressions is using the binary trees. The following algorithm can be
Question:
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. Create 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 create a Stack as follows. stack 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. |
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi