The first step is to read in the input expression and push it onto stk1, which is a stack of characters. A second stack of bnode* stk2 is used to store pointers to the nodes of the tree. The algorithm is as follows:

As long as stk1 is not empty:

Pop the top of stk1.

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 push the pointer to that bnode onto stk2.

On the other hand if the character popped is an operator (+,-,*,/) then:

Create a new bnode and store the operator in it.

Pop the two top entries of stk1, and set the 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 in Preorder. The output should agree with the input expression if

everything has been done correctly.

The program uses the class template stack from the standard C++ library.

Please complete the following program. ( You do not have to write a whole program, just need to fill in the blanks thanks!)

--------------------------------- #include  #include  #include  using namespace std; struct bnode { char c; bnode* left; bnode* right; }; void Preorder(bnode* root) { if (root) { cout << root->c << " "; Preorder(root->left); Preorder(root->right); } } int main() { stack stk1; stack stk2; char c; cout << "Enter prefix expression, then hit ENTER followed by CTL-D: " << endl; while (cin >> c) {  // For you to do: Push every character read onto stk1.  } while (!stk1.empty()) { c = stk1.top(); stk1.pop(); if (islower(c)) { // For you to do: Create a new bnode, store c in that bnode, // set the left and right pointers of the bnode to 0, and push // pointer to the newly created bnode onto stk2.  } else if (c == '+' || c == '-' || c == '*' || c == '/') {  // For you to do: Create a new bnode, store c in that bnode, // set the left bnode pointer to the top of stk2 and pop stk2, // set the right bnode pointer to the top of stk2 and pop stk2. // Finally push the pointer to the newly created bnode // onto stk2. } }  // The following code will print the expression tree in preorder, // so the output should equal the input prefix expression if // everything above has been done correctly. cout << " The preorder of the expression tree is "; Preorder(stk2.top()); cout << endl; return 0; } 

**Also May you please run on your compiler and screen shot an example