Monday, July 19, 2010

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.......
          :)





      

5 comments: