question archive An effective way to represent Mathematical expressions is using the binary trees
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.
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
The complete working code is:
#include<bits/stdc++.h>
using namespace std;
class TNode
{
public:
char data;
TNode* left;
TNode* right;
TNode(){}
};
TNode* constructTree(string postfix)
{
stack<TNode*> s;
int len = (int)postfix.length();
for(int i = 0; i<len; i++)
{
TNode* curr = new TNode();
curr->data = postfix[i];
if(postfix[i] >= 'a' && postfix[i] <= 'z') // Current character is operand
{
curr->left = NULL;
curr->right = NULL;
s.push(curr);
}
else // Current character is operator
{
TNode *T2 = s.top();
s.pop();
TNode *T1 = s.top();
s.pop();
curr->left = T1;
curr->right = T2;
s.push(curr);
}
}
return s.top();
}
void printPostOrder(TNode* head)
{
if(head == NULL)
return;
printPostOrder(head->left);
printPostOrder(head->right);
cout << head->data;
}
int main()
{
TNode* head;
string str;
cout << "Enter a postfix expression: ";
getline(cin, str);
head = constructTree(str);
cout << "Expression tree constrcted" << endl;
cout << "The post order traversal of the expression tree constructed is: ";
printPostOrder(head);
return 0;
}
Please see the attached file for the complete solution
