Infix to postfix

Use a stack. Read the operators and operands, placing the oeprators on the stack and the operands in order on the output. When encountering an operator, pop the stack to an matching level of precedence and place the operators on the end of the output sequence. When you run out of input, pop remaining operators and go.

To evaluate, use a stack of operands and when you encounter each operator, pop the top elements from the stack, evaluate, and push the result.

-bcl

http://www.faqts.com/knowledge_base/view.phtml/aid/26065/fid/585

Amit

can any of you write the working code as well ?

Why yes, I am betting many of us could. The problem is that we are not supposed to provide solutions for homework (look at the membership agreement). If you show us your code we can help you get it working and we can help you with specific questions.

Show us your code and we would be happy to help you get it working.

-bcl

OK, i'll post the code soon.

Please improve the main function so that it does the infix and prefix operation.

Since presently it is doing post fix operation.

#include <string.h>
#include <math.h>
#include <iostream.h>
#include <conio.h>
#include <assert.h>
#include <stdlib.h>


template <class IT>                  
struct stacknode
{
      IT data;
   stacknode<IT> * next;
};
/*****************************************************************/
template <class IT>
class stack
{
      private:
              stacknode<IT> * top;
      int counter;
   public:
            stack();
      ~stack();
      void push(IT);
      IT pop();
      void top1();      // returns the top element of stack if its not empty
      void clear();     // deletes the stack
      bool isempty();      // checks if the stack is empty
      bool isfull();    // checks if the memory is available
      void count();     // displays the no of stack entries
      void display();
};
/*****************************************************************/
template<class IT>
stack<IT> :: stack()
{
      top = NULL;
   counter = 0;
}
/*****************************************************************/
template<class IT>
stack<IT> :: ~stack()
{
      clear();
}

/*****************************************************************/
template<class IT>
void stack<IT> :: push(IT item)
{
      //assert(!isfull());
   if(!isfull())
   {
         stacknode<IT> * tmp = new stacknode<IT>;
      tmp -> data = item;
      tmp -> next = top;
      top = tmp;
      counter++;
   }
   else
         cout << endl << "Stack Limit Exceeds !" << endl;
}
/*****************************************************************/
template<class IT>
IT stack<IT> :: pop()
{
        if(!isempty())
   {
         stacknode<IT> * tmp = top;
      IT val = top -> data;
      top = top -> next;
      delete tmp;
      counter--;
      return val;
   }
   else
         {
                 cout << endl << "Stack Empty !" << endl;
         return 0;
      }
}
/*****************************************************************/
template<class IT>
void stack<IT> :: top1()
{
      if(!isempty())
                                                                          // if(top != NULL)
         cout << endl << " Top of Stack = " << top -> data << endl;
   else
           cout << endl << "Stack Empty !" << endl;
}
/*****************************************************************/
template<class IT>
void stack<IT> :: clear()
{
      stacknode<IT> * tmp = top;
   while(top != NULL)
         {
            top = top -> next;
         delete tmp;
         counter--;
         tmp = top;
      }
}
/*****************************************************************/
template<class IT>
bool stack<IT> :: isempty()
{
   if(top == NULL)
         return true;
   else
         return false;

}
/*****************************************************************/

template<class IT>
bool stack<IT> :: isfull()
{
   if (counter <= 5)                  //counter starts at 0, ie 6 possible stack entries
         return false;
   else
         return true;
      /*
      stacknode<IT> * temp = new stacknode<IT>
   temp -> next = top;
   if(temp == NULL)
         return true;    // it means space in mem is still aval
   else
         { return false;  }
   delete temp;
   */
}
/*****************************************************************/

template<class IT>
void stack<IT> :: display()
{
      stacknode<IT> * tmp = top;
      while(tmp)
         {
         cout << tmp -> data;
         tmp = tmp -> next;
      }
}

/*****************************************************************/
template<class IT>
void stack<IT> :: count()
{
      cout << endl << "Stack Counter = " << counter << endl;
}
/*****************************************************************/

void main()                                    // for postfix operation (x y +)?
{
      stack<int> operand;

   char * input;                        //array of chars
   int i = 0;
   bool quit = false;            // quit initialised to false
   float x, y;

   while(!quit)
   {
         cout << "Enter: ";
      cin >> input;
      switch(input [i])
      {
            case 'q': case 'Q':
               quit = true;
            break;

         case '+':
               y = operand.pop();                                  // y
            x = operand.pop();                                  // x
            cout << x << "+" << y << " = " << (x+y) << endl;    // +
            operand.push(x+y);
            break;

         case '-':
            x = operand.pop();
               y = operand.pop();
            cout << x << "-" << y << " = " << (x-y) << endl;
            operand.push(x-y);
            break;

         case '*':
               y = operand.pop();
            x = operand.pop();
            cout << x << "*" << y << " = " << (x*y) << endl;
            operand.push(x*y);
            break;

         case '/':
               y = operand.pop();
            x = operand.pop();
            cout << x << "/" << y << " = " << (x/y) << endl;
            operand.push(x/y);
            break;

         default:
            x = atoi(input);
            operand.push(x);
            getch();
            quit = false;
            break;
      }

   }

   operand.top1();
      operand.display();

   getch();
}

Well i am not familiar with tokenising etc, since i am new to programming. Just tell me how can i modify the same main function to perform prefix and infix operation.

Lets forget about the evaluation part for the time being. I need to know whether we can just by modifying the CASES (+, -, /, *)  get the prefix and infix task done ? If not then what you suggest i should do to make my main more simpler and understandable for a begginer like myself.

mak.