Solved

Infix to postfix

Posted on 2004-10-24
754 Views
Last Modified: 2008-02-01
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
0
Question by:mak47pk
    8 Comments
     
    LVL 11

    Expert Comment

    by:bcladd
    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
     
    LVL 10

    Expert Comment

    by:Sys_Prog
    0
     

    Author Comment

    by:mak47pk
    can any of you write the working code as well ?
    0
     
    LVL 11

    Expert Comment

    by:bcladd
    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
     

    Author Comment

    by:mak47pk
    OK, i'll post the code soon.
    0
     

    Author Comment

    by:mak47pk
    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
     
    LVL 11

    Accepted Solution

    by:
    (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
     

    Author Comment

    by:mak47pk
    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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Highfive Gives IT Their Time Back

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
      Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
    The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
    The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

    933 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now