infix to postfix conversion

/**********************************************************************

-> This C++ Program is to convert a given infix expression
   (either parenthesized or unparenthesized) to postfix form

-> Ex. of infix expression is ::(a+b^c^d)*(c+d)

-> Data Structers used
     Stack:array

-> This program works in microsoft vc++ 6.0 environment.

************************************************************************/

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>

class expression
{
private:
 char infix[100];
 char stack[200];
 int top;
 int r;
 char postfix[100];
public:
 void convert();
 int input_p(char);
 int stack_p(char);
 int rank(char);
};

int expression::input_p(char c)
{
 if(c==’+’ || c==’-')
  return 1;
 else if(c==’*’ || c==’/')
  return 3;
 else if(c==’^')
  return 6;
 else if(isalpha(c)!=0)
  return 7;
 else if(c==’(‘)
  return 9;
 else if(c==’)')
  return 0;
 else
 {
  cout<<”Invalid expression ::input error\n”;
  exit(0);
 }
}

int expression::stack_p(char c)
{
 if(c==’+’ || c==’-')
  return 2;
 else if(c==’*’ || c==’/')
  return 4;
 else if(c==’^')
  return 5;
 else if(isalpha(c)!=0)
  return 8;
 else if(c==’(‘)
  return 0;
 else
 {
  cout<<”Invalid expression  ::stack error\n”;
  exit(0);
 }
}

int expression::rank(char c)
{
 if(c==’+’ || c==’-')
  return -1;
 else if(c==’*’ || c==’/')
  return -1;
 else if(c==’^')
  return -1;
 else if(isalpha(c)!=0)
  return 1;
 else
 {
  cout<<”Invalid expression ::in rank\n”;
  exit(0);
 }
}

void expression::convert()
{
 cout<<”\n*************************************************\n”
  <<”This program converts the given infix expression\n”
  <<”in to postfix form”
                <<”\n*************************************************\n”;
 cout<<”Enter an infix expression ::\n”;
 cin>>infix;
 int l=strlen(infix);

 infix[l]=’)';
 infix[l+1]=”;

 //Convertion starts
 top=1;
 stack[top]=’(‘;

 r=0;
 int x=-1;

 int i=0;
 char next=infix[i];

 while(next!=”)
 {
  //Pop all the elements to outputin stack which have higher precedence
  while( input_p(next) < stack_p(stack[top]) )
  {
   if(top<1)
   {
    cout<<”invalid expression ::stack error\n”;
    exit(0);
   }

   postfix[++x]=stack[top];
   top–;

   r=r+rank(postfix[x]);
   
   if(r<1)
   {
    cout<<”Invalid expression  ::r<1\n”;
    exit(0);
   }
  }

  if(input_p( next ) != stack_p( stack[top]))
   stack[++top]=next;
  else
   top–;

  i++;
  next=infix[i];
 }
 postfix[++x]=”;

 if(r!=1 || top!=0)
 {
  cout<<”Invalid expression ::error in rank or stack\n”;
  exit(0);
 }

 cout<<”\n\nThe corresponding postfix expression is ::\n”;
 cout<<postfix<<endl;
}
int main()
{
 expression obj;
 obj.convert();
 return 0;
}
/************************************************************************

SAMPLE OUTPUT::
—————
 
*************************************************
This program converts the given infix expression
in to postfix form
*************************************************
Enter an infix expression ::
(a+b^c^d)*(c+d)
The corresponding postfix expression is ::
abcd^^+cd+*
Press any key to continue
**************************************************************************/

About these ads