Infix to postfix

Hi all

how can we write a program to enter an expression in infix notation and conver it into post fix. and also evaluate it ?


e.g.

(5+5) to (5 5 +) and (+ 5 5)

making separate function for every operation.

thanx
Mansoor KhanCITAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
bcladdConnect With a Mentor Commented:
(1) You want to make sure that you pop your operands in the same order every time. I am betting that this is a liitle screwy, either with division or with subtraction since you pop x and y in different orders (and the operators don't commute).

(2) The standard way to handle infix expressions is to read the entire expression, tokenizing it, and converting it to postfix. The resulting postfix expression could then be fed to the code you have in main for evaluation. So, one suggestion is to move the evaluator out to its own function and pass it a tokenized expression (everything up to the Q I would suspect) either as a vector/list of string or, potentially as a big string that you tokenize in the function (I like the list of tokens, myself).

Then main becomes something like:

list<string> expression;
while (!quit) {
  cout << "Expression: "
  cin >> input;
  if (toupper(input[0]) == 'Q')
    quit = true;
  else
    expression.push_back(input);
}

evaluate(expression);


Your work goes into evaluate. Why? So that when you write the infix to postfix converter you can just call it right before evaluation.

Does this design make sense? Then you can focus on writing infixToPostfix.

-bcl
0
 
bcladdCommented:
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
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
Mansoor KhanCITAuthor Commented:
can any of you write the working code as well ?
0
 
bcladdCommented:
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
0
 
Mansoor KhanCITAuthor Commented:
OK, i'll post the code soon.
0
 
Mansoor KhanCITAuthor Commented:
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();
}
0
 
Mansoor KhanCITAuthor Commented:
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.
0
All Courses

From novice to tech pro — start learning today.