Question

Use the following algorithm:

(1) Create three stacks of characters: stk1, stk2, stk3.

(2) Read the input infix expression one character at a time and push every character read ( other than ')' ) onto stk1. Do not push the character read if it is ')'.

(3) As long as stk1 is not empty, do the following:

           Fetch the top character ( call it c ) of stk1 and pop stk1.

           if c is an alphabetic character (a-z), push it onto stk3. (You can use the function islower(c) to test if character is one of a-z.)

           if c is an operator, push it onto stk2.

           if c is '(' then fetch the top character of stk2, push it onto stk3, and pop stk2.

(4) Print stk3 top to bottom by repeatedly fetching the top of stk3, printing it, and popping stk3, until stk3 is empty.

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 <iostream>

#include <stack>

#include<cctype>

using namespace std;

int main ()

{

stack<char> stk1, stk2, stk3; //The three stacks used to implemnt the algorithm

char c;

cout <<"Enter infix expression. To finnish hit Enter and then enter CTL-D";

while (cin >> c)

{

//FOR YOU TO DO: PUSH CHARECTER READ ( EXCULDING ')') ON TO FIRST STACK

}

while (! stk1.empty())

{

char c;

//For you to do: fetch top of first stack into variable c, and pop the first stack

//For you to do:check if c is lowercase alphabetic (a-z) or one of +,-,*,/, or open parethesis (, and perform appropiate //action according to algorithm:

}

// For you to do print the first stack from the bottom.

return 0;

}

Answer 1

Hi, Please find my implementation.

Please let me know in cae of any issue.

#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int main ()
{
   stack<char> stk1, stk2, stk3; //The three stacks used to implemnt the algorithm
   char c;
   cout <<"Enter infix expression. To finnish hit Enter and then enter # at end to stop"<<endl;
   while (cin >> c)
   {
       // stopping criteria
       if(c == '#')
           break;

   //FOR YOU TO DO: PUSH CHARECTER READ ( EXCULDING ')') ON TO FIRST STACK
       if( c != ')')
           stk1.push(c);
   }
   while (!stk1.empty())
   {
   //For you to do: fetch top of first stack into variable c, and pop the first stack
      c = stk1.top();
      stk1.pop();
     
   //For you to do:check if c is lowercase alphabetic (a-z) or one of +,-,*,/, or open parethesis (, and perform appropiate
   //action according to algorithm:
      if(islower(c))
          stk3.push(c);
      else if(c =='+' || c=='-' || c=='*' || c=='/')
          stk2.push(c);
      else if(c == '('){
          c = stk2.top();
          stk2.pop();
          stk3.push(c);
      }
     
   }
   // For you to do print the first stack from the bottom.
   while (! stk3.empty())
   {
       c = stk3.top();
       stk3.pop();
       cout<<c;
   }

   cout<<endl;
     
   return 0;
}