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;

   }

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





      

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.
                 


             

Sunday, July 18, 2010

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".

Saturday, July 17, 2010

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



Friday, July 16, 2010

#C 2 ( First program)

start with a simple program in C....

                                  #include<conio.h>
                             #include<stdio.h>
                             void  main(){
                                        clrscr();
                                         printf("welcome to my blog");
                                   }

I assumed that you are working on TC ide.so first we will compile program either by pressing keys Alt+F9 or by clicking 'compile' given in menu on the center of top.Compilation of source code will generate it's machine code



Compiler can catch only syntax errors.It can not catch 'run time' errors.
Syntax errors are related to rules of programming languages defined by C developer.
If program has been compiled without any error(syntax) with or without any warning you can run(execute) your program bye pressing either Ctrl+F5 or from menu(click run).


After being run, console window will be disappear within fraction of second. So to make console in pause, we use other functions like 'getch( )' or 'getche( )'.The only difference b/w these function is that the function getch( ) leaves console without any change on it but getche( ) echos the letter on console to which we pressed in pause condition.


so the new code will be like


                                   include<conio.h>
                             #include<stdio.h>
                             void  main(){
                                        clrscr();
                                         printf("welcome to my blog");
                                        getch();
                                   }

#C 1

Lets start with a simple program in C....

      #include &lsaquo stdio.h &rsaquo
      #include &lsaquo conio.h ›
        void main()
         {
            clrscr();
            printf("welcome to my blog");
         }

now lets discuss few important terms that we have used in the above program.



#   :-

  # is a symbol which tells to preprocessor that before compiling any source code written on IDE, include the header file written after syntax #include.



Header Files   :-

  Any file in C or C++ which ends with a extension .h is known as a Header file. These files are created by the company which develops the software of C language.These files contain a huge collection of predefine programs known as Functions for example-All the functions are related to mathmatical calculations like sqrt(),sin(),cos(),pow() etc available in a header file called math.h


So if programmer needs to use a predefine function which resides in a header file then he must include this header file.


Syntax   :-

  # include &lsaquo headerfile.h &rsaquo



Void   :-

  Void is a keyword and it is return type of function main().Don't bother about return type and function words i have used.We will discuss these words in detail later.key words are pre reserved words used by C compiler and they can not be used in a source code like name of variables and functions.




main()   :-

  main() is a function.At the time of compilation of programme, compiler reads the source code from very first line but CPU reads after function main().




{   :-

  This is known as "block opening bracket".when we use this it creates a stack which is very useful to put function calls in a particular order.



clrscr()   :-

  It is a function which resides in a header file &lsaquo conio.h &rsaquo


printf   :-

  This function is stands for print formatted.Here we are using this for writing message on console.This also have various other uses which we will discuss later.

}   :-

  This is known as "bock closing bracket".


;     :-

  This is used in a C programme as a "statement terminator".

About me

Hi...
Don't know from where i should start my blogging.But being a third year student of NIT Bhopal i should have a blog atleast to express my knowledge and ideas that i have.


So friends here is

Ramendra Singh
Ramendra Singh
.   Also available on Orkut and Facebook .



Since i didn't had any knowledge about programming when i join this institute so i know the basic needs of a beginner of programming. I will try to fulfill that needs.


Without going in detail of history of C we will start with programming. If you are seriously interested in history you can check this on wikipedia. we will start C form next post so wait for that.

Have a good day......