QuickSort using stack

//QuickSort using stack
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct stk
{
int a[50];
int top;
};
void push(struct stk *s,int item);
int pop(struct stk *s);
struct stk l;
struct stk u;
main()
{
      int i,*a,n;
      void create(int **a,int n);
      void display(int *a,int n);
      void quicksort(int *a,int n);
      extern int quick(int *s,int left,int right);
      l.top=-1;
      u.top=-1;
      a=NULL;
      printf("Enter the number of elements you want in your array : " );
      scanf("%d",&n);
      create(&a,n);
      display(a,n);
      quicksort(a,n);
      display(a,n);
     getch();
      return 0;
}
void create(int **a,int n)
{
     int i;
     int *s;
     s=(int *)malloc(n*sizeof(int));
     printf("\n Enter the value of array elements " );
     for(i=0;i<n;i++)
     {
                  scanf("%d",&s[i]);
     }
     *a=s;
}
void display(int *a,int n)
{ int i;
      printf("\n array elements " );
     for(i=0;i<n;i++)
     {
                  printf("%d ",a[i]);
     }
}
void quicksort(int *a,int n)
{
     int b,e,loc;
     push(&l,0);
     push(&u,n-1);
     while(l.top!=-1&&u.top!=-1)
     {
         b=pop(&l);
         e=pop(&u);
       
         loc=quick(a,b,e);
         if (b<loc-1)
         {
                push(&l,b);
                push(&u,loc-1);  
         }
         if(loc+1<e)  
         {
              push(&l,loc+1);
              push(&u,e);
         }  
     }                    
}
int quick(int *s,int left,int right)
{
    int loc,temp;
    loc=left;
    while(1)
    {
            while(s[loc]<=s[right]&&loc!=right)
              {
                  right=right-1;
             
              }
            if(loc==right)
              return loc;
            if(s[loc]>s[right])
            {
               temp=s[loc];
               s[loc]=s[right];
               s[right]=temp;
            }
         
            loc=right;
            while(s[left]<=s[loc]&&loc!=left)
              left=left+1;
            if(loc==left)
              return loc;
            if(s[left]>s[loc])
            {
               temp=s[loc];
               s[loc]=s[left];
               s[left]=temp;
            }
            loc=left;
    }   
}
void push(struct stk *s,int item)
{
 int c;
  s->a[++(s->top)]=item;
}
int pop(struct stk *s)
{
    int i;
    i=s->a[(s->top)--];
    return i;
}

Read More

Tweet

Evaluation of postfix Expression

//Evaluation of postfix Expression
#include<stdio.h>
#include<conio.h>
#include<math.h>
struct stk
{
int a[50];
int top;
};

main()
{
      int i,a,b,r;
      char exp[50],c='\0';
      void push(struct stk *s,int item);
      extern int isempty(struct stk *s);
      extern int isfull(struct stk *s);
      int pop(struct stk *s);
      struct stk s;
      s.top=-1;
      printf("Enter the expression: ");
      i=0;
      while(1)
      {
        c=getchar();
        fflush(stdin);
        if(c!='\n')
        exp[i]=c;
        else
        {
             exp[i]='\0';
             break;
        }
        i++;
      }
      printf("%s",exp);
   
      i=0;
      while(exp[i]!='\0')
      {
                       
         if(exp[i]=='^'||exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/')
         {
               a=pop(&s);
               printf("\n a %d",a);
             
               b=pop(&s);
                printf("\n b %d",b);
                     if(exp[i]=='^')
                          r=pow(b,a);
                     else if(exp[i]=='/')
                          r=b/a;
                     else if(exp[i]=='*')
                          r=b*a;
                     else if(exp[i]=='+')
                          r=b+a;
                     else if(exp[i]=='-')
                          r=b-a;
                       
                push(&s,r);                                                
         }
         else
         {
             r=exp[i]-48;
           
             push(&s,r);
           
         }
       
         i=i+1;
         }
         r=pop(&s);
         printf("\n result is %d",r);
     
     getch();
      return 0;
}

void push(struct stk *s,int item)
{
 int c;
 c=isfull(s);
 if(c==0)
 {
          printf("stack is full. it is not possible to PUSH %d ",item);
          return;
 }
 s->a[++(s->top)]=item;
}
int isfull(struct stk *s)
{
    if(s->top==9)
     return 0;
    return 1;
}
int pop(struct stk *s)
{
    int c,i;
    c=isempty(s);
    if(c==0)
     {
          printf("stack is empty. it is not possible to POP ");
          return -1000;
     }
    i=s->a[(s->top)--];
    return i;
}
int isempty(struct stk *s)
{
    if(s->top==-1)
     return 0;
    return 1;
}

Read More

Tweet

Stack implimentation using linked list

//Stack implimentation using linked list
#include<stdio.h>
#include<conio.h>
struct node
{
       int data;
       struct node *next;
};
main()
{
     struct node *tos;
     int i,c,n,j;
     void push(struct node **top,int item);
     extern int isfull();
     extern int isempty(struct node *top);
     int pop(struct node **top);
     tos=NULL;
     printf("Enter number of items to be pushed:");
     scanf("%d",&n);
     for(j=0;j<n;j++)
     {
      printf("Enter the item to be pushed:");
      scanf("%d",&i);
      push(&tos,i);
     }
     for(j=0;j<n;j++)
     {
     i=pop(&tos);
     }
     getch();
}
void push(struct node **top,int item)
{
     int t=0;
     struct node *temp=NULL;
     t=isfull();
     if(t==0)
     {
             printf("stack is already full.It is not possible to PUSH the given item");
             return;
     }
     temp=(struct node *)malloc(sizeof(struct node));
     temp->data=item;
     temp->next=*top;
     *top=temp;
}
int isfull()
{
    struct node *temp=NULL;
    temp=(struct node *)malloc(sizeof(struct node));
    if(temp==NULL)
     return 0;
    free(temp);
    return 1;
}
int pop(struct node **top)
{
    int i,c;
    struct node *t;
     c=isempty(*top);
     if(c==0)
     {
      printf("stack is empty.It is not possible to POP the item");  
      return 0;
     }
     i=(*top)->data;
     t=*top;

    *top=(*top)->next;
         free(top);
    printf("\npoped item is %d",i);
    return i;
}
int isempty(struct node *top)
{
    if(top==NULL)
     return 0;
    return 1;
}

Read More

Tweet

Infix to Postfix conversion

//Infix to Postfix conversion
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<string.h>
struct stk
{
char a[50];
int top;
};
 int isempty(struct stk *s);
   int isfull(struct stk *s);
main()
{
      int i,a,b,r,j;
      char exp[50],res[50],c='\0',st[1];
      void push(struct stk *s,char item);
   
      char pop(struct stk *s);
      struct stk s;
      s.top=-1;
      printf("Enter the expression: ");
      gets(exp);
      st[0]=')';
      st[1]='\0';
      strcat(exp,st);
            i=0;
      j=0;
      while(exp[i]!=0)
      {
           if(exp[i]=='^'||exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/'||exp[i]=='('||exp[i]==')')
                      {
                         if(exp[i]=='(')
                             push(&s,'(');
                         
                           if(exp[i]=='^'||exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/')
                           {
                                if(exp[i]=='^')
                                 {
                                                c='\0';
                                                while(1)
                                                {
                                                   c=pop(&s);
                                                   if(c=='('||c=='*'||c=='/'||c=='+'||c=='-'||c=='\0')
                                                   {
                                                     push(&s,c);
                                                     break;
                                                   }
                                                   else
                                                   {
                                                       res[j]=c;
                                                       j++;
                                                   }
                                                }
                                 }
                                 if(exp[i]=='*'||exp[i]=='/')
                                 {
                                      c='\0';
                                                while(1)
                                                {
                                                   c=pop(&s);
                                                   if(c=='('||c=='+'||c=='-'||c=='\0')
                                                   {
                                                     push(&s,c);
                                                     break;
                                                   }
                                                   else
                                                   {
                                                       res[j]=c;
                                                       j++;
                                                   }
                                                }
                                 }
                                  if(exp[i]=='+'||exp[i]=='-')
                                 {
                                     c='\0';
                                                while(1)
                                                {
                                                   c=pop(&s);
                                                   if(c=='('||c=='\0')
                                                   {
                                                     push(&s,c);
                                                     break;
                                                   }
                                                   else
                                                   {
                                                       res[j]=c;
                                                       j++;
                                                   }
                                                }
                                 }
                                 push(&s,exp[i]);
                            }
                               
                       
                         
                          if(exp[i]==')')
                              {
                                c='\0';
                                while(1)
                                {
                                           c=pop(&s);
                                           if(c=='('||c=='\0')
                                           break;
                                            res[j]=c;
                                            j++;
                                             
                                         
                                 }
                              }
                      }                                                                                
                     
                      else
                      {
                          res[j]=exp[i];
                          j++;
                      }
                       
              i++;
      }
      res[j]='\0';
      printf("\n Infix exp is %s",exp);
      printf("\n Postfix expression is %s",res);
     getch();
      return 0;
}

void push(struct stk *s,char item)
{
 int c;
 c=isfull(s);
 if(c==0)
 {
          printf("stack is full. it is not possible to PUSH %c ",item);
          return;
 }
 s->a[++(s->top)]=item;
}
int isfull(struct stk *s)
{
    if(s->top==9)
     return 0;
    return 1;
}
char pop(struct stk *s)
{
    int c;
    char i;
    c=isempty(s);
    if(c==0)
     {
          printf("stack is empty. it is not possible to POP ");
          return '\0';
     }
    i=s->a[(s->top)--];
    return i;
}
int isempty(struct stk *s)
{
    if(s->top==-1)
     return 0;
    return 1;
}

Read More

Tweet

Tower of Hanoi

//Tower of Hanoi
#include<stdio.h>

#include<conio.h>

main()

{

      int n;

      void Tower(char beg,char inter,char end,int n);

      printf("Enter how many pins you want to move: ");

      scanf("%d",&n);

      Tower('A','B','C',n);

      getch();

      return 0;

}

void Tower(char beg,char inter,char end,int n)

{

     if (n==1)

     {

              printf("\n%c->%c",beg,end);

              return;

     }

     Tower( beg,end,inter,n-1);

          printf("\n%c->%c",beg,end);

      Tower(inter,beg,end,n-1);     

}

Read More

Tweet