Convert infix expression to prefix expression using stack in cpp[ c++ program] and using same postfix function to convert to prefix.

 INFIX TO PREFIX

 A+B*C+D-->> ++A*BCD

ALGORITHM FOR INFIX TO PREFIX CONVERSION:

1. Read the infix expression from left to right one character at a time.
2. Repeat step 3
3.  * If  symbol is operand put into operand stack.* If  symbol is left parenthesis push into operator stack.* If right parenthesis, pop two operand and one operator and push in operand stack until left parenthesis is occur.* If scan symbol is operator then "If operator has same or less precedence then operator available on top of operator stack,then pop one operator and two operand from prefix expression & push into operand stack.  
4. Repeat Until end of expression.
5. Pop all the remaining operator and corresponding operand and form prefix expression.
6. Exit.

       

PROGRAM FOR INFIX TO PREFIX CONVERSION:   

#include<iostream.h>
#include<conio.h>
#include<ctype.h>

 struct node
{
 char data;
 struct node *next;
}*top = NULL;

int prece(char token);

class stack
{
   public:

      void push(char x)
  {
    struct node *p;
    p=new node;
    p->data=x;
    p->next=top;
    top=p;
  }
     char pop()
       {
  char x;
  x=top->data;
  top=top->next;
  return x;
       }
     void display()
       {
  struct node *p;
  p=top;

 while(p!=NULL)
    {
      cout<<"\n"<<p->data <<"\n";
      p=p->next;
    }
       }
       char infix_postfix(char postfix[30],char infix[30]);
       char top1()
 {
 return top->data;
 }


int empty()
{
if(top==NULL)
return 1;
else
return 0;
}
};

char stack::infix_postfix(char postfix[30],char infix[30])    //INFIX TO  POSTFIX CONVERSION 
  {
    char token;
    int j=0;char a;
    stack s;
     for(int i=0;infix[i]!='\0';i++)
       {
  token=infix[i];
    if(isalnum(token))
    {
        postfix[j++]=token;
    }
    else if(token=='(')
    {
        s.push(token);
    }
    else if(token==')')
    {

       while(s.top1()!='(')
       {
   postfix[j++]=s.pop();
       }
    s.pop();
    }
   else
    {
       while(prece(token)<=prece(s.top1()) && !s.empty())
       {
         postfix[j++]=s.pop();
       }
      s.push(token);
    }
   }
     while(s.top1()!=NULL)
      {
 postfix[j++]=s.pop();
       }
 postfix[j]='\0';
 return *postfix;
}


int prece(char token)
 {
   if(token=='^')
    return 4;
   else if(token=='*'||token=='/')
    return 3;
   else if(token=='+'||token=='-')
    return 2;
   else
    return 0;
 }
 void main()
  {
   stack s1;
   int m,n,i,j;
   clrscr();
   char infix1[30]={0},prefix[30]={0},temp[30]={0};
   cout<<"Enter infix Expression\n";
        cin>>infix1;

  for(i=0;infix1[i]!='\0';i++);          //FIND LENGTH OF EXPRESSION
  --i;
  m=i;
  for(j=0;infix1[j]!='\0';j++)     //COPY IN REVERSE ORDER
  {
   temp[j]=infix1[i];
   i--;
  }

  for(i=0;temp[i]!='\0';i++)                  //EXCHANGE '(' BY ')' AND ')' BY "('
  {
    if(temp[i]=='(')
     temp[i]=')';
    else if(temp[i]==')')
     temp[i]='(';
  }
  s1.infix_postfix(prefix,temp);               //CALL INFIX TO POSTFIX CONVERSION FUNCTION
        for(i=m;i>=0;i--)                            //PRINT IN REVERSE ORDER
  {
  cout<<prefix[i];                           //PREFIX
  }
  getch();
}