Complete the starter code in protect H .starter code has been placed in your hom
ID: 3790564 • Letter: C
Question
Complete the starter code in protect H .starter code has been placed in your homework folder. The object of this assignment is to construct an expression tree from a given prefix expression. The algorithm is similar to the one in Hwk03. The prefix expression consists of operators and variables a-z. The first step is to read in the input expression and push it onto Stk 1, which is a stack of characters. A second stack of bnode stk 2 is used to store pointers to the nodes of the tree. The algorithm is as follows As long as stk 1 is not empty: Pop the top Of stk 1. If the character popped is an operand (a-z). create a new bnode to store it. set the left and right pointer of that bnode to 0. and posh the pointer to that bnode onto stk2. On the other hand if the character popped is an operator A then: Create a new bnode and store the operator in A. Pop the two top entries of stk 1. and set me left and right pointers of the bnode just created to those two entries. Push the pointer to the newly created bnode onto stk2 If the input prefix expression is well-formed, at the end stk2 will contain just one pointer to the root of the expression tree. Finally we print the expression tree n Preorder The output should agree with the input expression if everything has been done correctly. As always, do not submit through Blackboard, leave everything onExplanation / Answer
// C++ program for expression tree
#include<bits/stdc++.h>
using namespace std;
// An expression tree node
struct bnode
{
char value;
bnode* left, *right;
};
// A utility function to check if 'c'
// is an operator
bool isOperator(char c)
{
if (c == '+' || c == '-' ||
c == '*' || c == '/')
return true;
return false;
}
// Utility function to do preorder traversal
void preorder(bnode *t)
{
if(t)
{
printf("%c ", t->value);
preorder(t->left);
preorder(t->right);
}
}
// A utility function to create a new node
bnode* newNode(int v)
{
bnode *temp = new bnode;
temp->left = temp->right = NULL;
temp->value = v;
return temp;
};
// Returns root of constructed tree for given
// prefix expression
bnode* constructTree(char prefix[])
{
stack<bnode *> st;
stack<char> a;
for (int i=0; i<strlen(prefix); i++)
{
a.push(prefix[i]);
}
bnode *t, *t1, *t2;
// Traverse through every character of
// input expression
while(!a.empty())
{
// If operand, simply push into stack
if (!isOperator(a.top()))
{
t = newNode(a.top());
a.pop();
st.push(t);
}
else // operator
{
t = newNode(a.top());
a.pop();
// Pop two top nodes
t1 = st.top(); // Store top
st.pop(); // Remove top
t2 = st.top();
st.pop();
// make them children
t->right = t2;
t->left = t1;
// Add this subexpression to stack
st.push(t);
}
}
// only element will be root of expression
// tree
t = st.top();
st.pop();
return t;
}
// Driver program to test above
int main()
{
char prefix[] = "+*+a/bcd*e5";
printf("Expression is %s ", prefix);
bnode* r = constructTree(prefix);
printf("prefix expression is ");
preorder(r);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.