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;

   }

Evaluation of postfix expression using Stack

Psudo code :-
                      

  1)        Scan for the given postfix expression from left to right , 
               one element at a time.

  2)        Check whether it is an operand or an operator.

  3)       If it is an operand the n push the element in to stack and if it is
              an operator then pop the two elemnt from the stack .
              Apply the given operator on them and then push
              back the returned result in to the stack.
  4)       Repeat the step 1 to 3 untill the whole postfix expression 
             comes to the end.

  5)       Pop the element from the stack which shold be the only element 
             in the stack and return it from the function as the result of th
             expression. 



          Program in C :-
                 


  struct stack
        { 
             float  arr[10];
             int tos;
          };
     
       #include< process.h>
       #include< math.h>
       #include< stdio.h>
       #include< conio.h>

    void push ( struct stack *, float );
    float pop  (struct stack *);
    int isopnd(char);
    float solve ( char[ ] );
       float evaluate (float,float,char );

       void main ( )
        {
           char postfix[80];
        float result ;
        clrscr( ) ;

        printf( " \n Enter valid expression  " );
        scanf("%s", postfix);
        result = solve(postfix);

        printf("result is = %f" , result);
        getch( );
}


float solve (char postfix[80])
        {
        struct stack s;
        int i ;
        char ch ;
        float op1 ,  op2 , ans , x ;
        s.tos = -1 ;

        for ( i=0 ; postfix[i] !='\0' ; i++ )
           {
            ch = postfix [i] ;
            if ( isopnd (ch) ==1)
                {
                   x= ch-48;
                   push (&s,x);
                  }
               else
                  {
                  op2 = pop(&s);
                  op1=pop(&s);
                  ans = evaluate (op1,op2,ch);
                  push(&s,ans);
                 }                                                                }
            ans=pop(&s);
            return(ans);
          }


    int isopnd (char ch)
       {
         if(ch>='0'&&ch<='9')
         return 1;
         else
         return 0 ;
         }



 float evaluate (float a, float b, char op)
               {

              switch(op)
               {
                  case '+' :

                         return(a+b);

                case'-' :

                          return(a-b);

                 case'*' :

                           return(a*b);

               case'/' :

                        return(a/b);

                 case '$'   :

                        return(pow(a,b));

                 }
        }



      void push ( struct stack *p , int x)
          {
               if ( p -> tos == 9)
                  {
                     printf( "stack overflow");
                         exit ;
                    }
                 p -> arr[ ++ p -> tos ] = x;
          }



    float pop ( struct stack *p)
         {
          int n ;
          if ( p -> tos == -1)
              {
             printf( " stack under flow");
              return -1 ;
               }
            n= p-> arr [ p-> tos --] ;
            return (n);

           }
 
 We also have completed evaluation of a postfix expression through stack.

In the stack sequence wait for my new post.......
          :)

      

Uses of STACKS

Stack is used by compiler as well as programmer.Its most important uses are listed below ---

      1)  Stack is used by compiler to store local variable declared inside a function.

      2)  Stack is also used by compiler to store return addresses whatever it encounters
               a function call

      3)  It is also used by programmer while writing down programs to convert a givin
               infix expression to its corresponding prefix or postfix expression.

     4)  Stack used by programmer whenever they implement sorting algorithms like
               quick sort, mergesort  etc in a non recursive way.



Ques :-    What is the need for a programmer to convert a infix expression to postfix or
                    prefix expression  ?

Ans :-       It is bit difficult to CPU to understand infix expression because of the operator priorities.
                   Moreover, different programming languages might have different operators with
                   varying properties. To make job of CPU easier DS two alternates for infix expression
                                   1) post fix    2) prefix

                           In these forms infix expression is arranged in such a way that the entire
                  expression is set according to the priority of the operator. So, the CPU start
                  reading  expression form one end  to the other end.

Priorities of operators  :-

                               1)    ( , )

                               2)     $ , ^ 

                               3)     / ,     * ,     %

                               4)     + , -

            NOTE :- 
                    Operators on same level have equal priorities means the operator who will come first in 

                    expression will be evaluate first. And the operator have higher priority will evaluate first.

                    Parentheses have highest priority.

                 


             

Programs of PUSH & POP functions in C

Function PUSH

        void push ( struct stack *p , int n)
              {
                      if ( p -> tos == MAX-1)
                            {
                                printf( "stack overflow");
                                return;
                             }
                        p -> arr[ ++ p -> tos ] = x;
               }
            


Function POP   :-
        


int pop ( struct stack *p)
             {
                  int n ;
                  if ( p -> tos == -1)
                      {
                         printf( " stack under flow");
                          return -1 ;
                       }
                    n= p-> arr [ p-> tos --] ;
                    return (n);

               }

So friends  we have done with stack implementation  in C.

In the next post we will discuss about various uses of stacks.

Psudo codes for function PUSH & POP

Psudo code for function "push" :-
    1)  Check  the condition for over flow. 
      2)   If stack is full then print the appropriate message and return.
      3)  If stack is not full then increase 'tos' by 1. 
      4) Place the element at the position pointed by 'tos' .
     

Psudo code for function "pop"  :-
      1) Check the condition for under flow.
      2) If  stack is empty then print the message "stack under flow"  and return with appropriate error
            message.
      3) Remove the element pointed by 'tos'.
        4)  Decrement 'tos' by 1.
        5)  Return the removed element.

   

STACK

    Stack is a linear data structure which is logiacally open at one end only.Means in stack we
can insert or delete data from one end conventionally called TOP OF STACK (TOS).

We will impliment Stack in C.

Here i am writing   1)Psudo code   2) Algorithm   3) Source code in C

Implimentation of Stack in C   :-

struct stack

 {

    int arr[10];

    int tos;

  };

void push (struct stack *,int);

int pop(struct stack*);

#include < stdio.h >
#include < conio.h >
#define MAX 10

  void main()

  {

      int x,ch;

      struct stack s;

      s.tos=-1;

     

  do{
      printf("\n enter ur choice \n 1)for push an element \n 2)pop an element \n 3)for exit");

      scanf("%d".&ch);

      switch(ch)

        case 1:

                    printf("enter the number to be pushed in stack");

                    scanf("%d".&x);

                    push(&s,x);

                    break;

        case 2:

                    x=pop(&s);

                    printf("popped element is = %d",x);

                    break;

        case 3:

                    exit;
          printf("do you want to continue Y/N);
          scanf("%c",&choice);
          } while(choice=='y');

     getch();
  }


for more information about STACK i would like to recommend NPTEL video from IIT Delhi by Dr. NAVEEN GARG.




 Wait for my next post for Psudo code, algorithm and source code of function "push" & "pop".

Run C compiler in fullscreen mode on window 7 or Vista through Dosbox

Lets do it step by step...
 

Step 1:-

    Put your TC folder in C drive if it is any where else in your system.


 

Step 2 :-

      If you do not have Dosbox setup then Download dosbox hrom here.

 

Step 3 :-

      Now install dosbox in your PC.

 

Step 4 :-

      Open dosbox and write command:-

                  Z:\>mount c c:\tc
                  Z:\>c:
                  C:\>cd bin
                  C:\BIN>tc.exe


 

Step 5 :-

      Now press Alt+ENTER and make window in fullscreen mode. Now go to 'option' in menu bar and open 'Directories' and change the setting of all four directories.These directories are 'INCLUDE DIRECTORIES','LIBRARY DIRECTORIES','OUTPUT DIRECTORIES' and 'SOURCE DIRCTORIES' respectively.

Write C:\   in place of   C:\>TC

 

Step 6 :-

      Enjoy C programming in fullscreen mode.

                                   Thank you for visiting me