Write a program to convert In-Fix to postfix notation in C or C++?

Question

For example:

Infix      Postfix 
------     -------- 
a+b          ab+ 
(a+b)*c      ab+c* 
a+b*c        abc*+ 
a*(b+c)-d/e  abc+*de/-

Answer 1

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

#define MAX 100

typedef struct stack
{
 int data[MAX];
 int top;
}stack;

int priority(char);
void init(stack *);
int empty(stack *);
int full(stack *);
char pop(stack *);
void push(stack *,char);
char top(stack *);

void main()
{
  stack s;
  char x;
  int token;
  init(&s);
  clrscr();
  printf("nEnter infix expression:");

  while((token=getchar())!='n')
  {
    if(isalnum(token))
       printf("%c",token);
    else
       if(token == '(')
           push(&s,'(');
       else
       {
         if(token == ')')
             while((x=pop(&s))!='(')
                printf("%c",x);
         else
         {
            while(priority(token)< =priority(top(&s)) && !empty(&s))
             {
               x=pop(&s);
               printf("%c",x);
             }

             push(&s,token);
         }
       }
  }

  while(!empty(&s))
  {
    x=pop(&s);
    printf("%c",x);
  }

  getch();
}

//---------------------------------------------
int priority(char x)
{
   if(x == '(')
     return(0);

   if(x == '+' || x == '-')
     return(1);

   if(x == '*' || x == '/' || x == '%')
     return(2);

   return(3);
}

//---------------------------------------------
void init(stack *s)
{
   s->top=-1;
}

//---------------------------------------------
int empty(stack *s)
{
    if(s->top==-1)
       return(1);
    else 
       return(0);
}

//---------------------------------------------
int full(stack *s)
{
    if(s->top==MAX-1)
      return(1);
    else 
      return(0);
}

//---------------------------------------------
void push(stack *s,char x)
{
  s->top=s->top+1;
  s->data[s->top]=x;
}

//---------------------------------------------
char pop(stack *s)
{
   int x;
   x=s->data[s->top];
   s->top=s->top-1;
   return(x);
}

//---------------------------------------------
char top(stack * s)
{
   return(s->data[s->top]);
}
//---------------------------------------------

Answer 2

/*
 * operand can be a single alphabete only.
 */
bool isOperand(char ch)
{
   return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

/*
 * return the precedence of an operator. Numbers are just to use precedence for relative purpose.
 */
int operatorPrecedence(char ch)
{
   switch (ch)
   {
      case '+':
      case '-':
         return 1;

      case '*':
      case '/':
         return 2;

      case '^':
         return 3;
   }
   return -1;
}

*
 * This function uses Stack data structure. Returns -1 if the expression is invalid
 */
int infixToPostfix(char* expression)
{
   int i, k;

   MyStack stack;

   // read each character of the expression (which is either operator, operand or parenthesis
   for (i = 0, k = -1; expression[i]; ++i)
   {
      if (isOperand(expression[i]))
      {
         expression[++k] = expression[i];
      }
      else if (expression[i] == '(')
      {
         stack.push(expression[i]);
      }
      else if (expression[i] == ')')
      {
         while (!stack.isEmpty() && stack.getTop() != '(')
            expression[++k] = stack.pop();

         if (!stack.isEmpty() && stack.getTop() != '(')
            return FAILOUR;
         else
            stack.pop();
      }
      else // an operator is encountered
      {
         while (!stack.isEmpty() && operatorPrecedence(expression[i]) <= operatorPrecedence(stack.getTop()))
            expression[++k] = stack.pop();
         stack.push(expression[i]);
      }

   }

   // All remaining elements in the stack are operators.
   // pop them all out
   while (!stack.isEmpty())
      expression[++k] = stack.pop();

   expression[++k] = '\0';
   cout<<expression ;

   return SUCCESS;
}