Saturday, July 24, 2010

Conversion of INFIX expression to POSTFIX expression

PSUDO CODE :-
                       
                           1)  Scan infix expression from left to right one character at
                                    a time.

                           2)  Check whether the character is an operator or operand.

                           3)  If it is an operand then copy it in to postfix array.

                           4)  If it is an operator then
                                   a) check whether stack is empty or not.
                                   b) If it is empty then push the operator in the stack and
                                       read next element from the infix array.
                                   c) If stack is empty then match the priority of stack top
                                       with operator out side.
                                   d) If the precedence of outer operator is higher then
                                        push it in to the stack and go to read next charecter
                                        from infix array.
                                   e)  If the precedence of top is higher then pop it.Append
                                        in  the postfix array and go to step 1.

                             5)  Repeat the above procedure until the infix expression
                                     comes to an end.

                           6)  Pop all the element (remaining) from the stack one
                                     by one and copy them in the postfix array.


 PROGRAM :- 
                                                                 

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


struct stack
   {
    char arr[20];
    int tos;
   };
void push(struct stack *,char);
char pop(struct stack *);
void convert(char[],char[]);
int isopnd(char);
int prcd(char,char);
int isempty(struct stack);

void main()
   {
    char infix[50],postfix[50];
    clrscr();
    printf("\nenter a vaid expression");
    scanf("%s",infix);
    convert(infix,postfix);
    printf("the postfix expression is   %s ",postfix);
    getch();
   }

 void convert(char infix[50],char postfix[50])
   {
     int i,j=0,result;
     char ch,op;
     struct stack s;
     s.tos=-1;
     for(i=0;infix[i]!='\0';i++)
       {
    ch=infix[i];
    if(isopnd(ch)==1)
    {
     postfix[j]=ch;
     j++;
     }
     else
      {
       while(isempty(s)==0)
        {
          result=prcd(ch,s.arr[s.tos]);
          if(result==0)
        break;
          op=pop(&s);
          postfix[j]=op;
          j++ ;
        }
       push(&s,ch);
     }}
    while(isempty(s)==0)
    {
     op=pop(&s);
     postfix[j]=op;
     j++;
    }
       postfix[j]='\0';
     }

int isempty(struct stack s)
 {
  if(s.tos==-1)
   return 1;
  else
   return 0;
  }

int isopnd(char ch)
   {
    if((ch>=65 && ch<=90)||(ch>=97 && ch<=122))
       return 1;
    else
       return 0;
    }

int prcd(char out, char in)
  {
   if(in=='$')
      return 1;
   else if ( out=='$')
      return 0;
   else if(in=='/'|| in=='*')
      return 1;
   else if(out=='/' || out=='*')
      return 0;
   else
      return 1;

   }

No comments:

Post a Comment