[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

Infix to postfix

Posted on 2004-10-24
8
Medium Priority
?
813 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
Comment
Question by:Mansoor Khan
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
8 Comments
 
LVL 11

Expert Comment

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

Author Comment

by:Mansoor Khan
ID: 12399983
can any of you write the working code as well ?
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 11

Expert Comment

by:bcladd
ID: 12400316
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:Mansoor Khan
ID: 12406658
OK, i'll post the code soon.
0
 

Author Comment

by:Mansoor Khan
ID: 12418590
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:
bcladd earned 100 total points
ID: 12421444
(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:Mansoor Khan
ID: 12423361
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

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
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.
Suggested Courses

656 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