C program for Merge Sort

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    /* create temp arrays */
    int L[n1], R[n2];

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of L[], if there are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

/* Function to print an array */
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}


Output:
Given array is
12 11 13 5 6 7

Sorted array is
5 6 7 11 12 13

Dynamic Programming 0/1 Knapsack Using C/C++

Dynamic Programming 0/1 Knapsack Using C/C++

/* A Naive recursive implementation of 0-1 Knapsack problem  using c*/
#include<stdio.h>

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   // Base Case
   if (n == 0 || W == 0)
       return 0;

   // If weight of the nth item is more than Knapsack capacity W, then
   // this item cannot be included in the optimal solution
   if (wt[n-1] > W)
       return knapSack(W, wt, val, n-1);

   // Return the maximum of two cases:
   // (1) nth item included
   // (2) not included
   else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                    knapSack(W, wt, val, n-1)
                  );
}

// Driver program to test above function
int main()
{
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int  W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}


OUTPUT:
220

C PROGRAM TO IMPLEMENT LEXICAL ANALYZER

C PROGRAM TO IMPLEMENT LEXICAL ANALYZER
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void keyw(char *p);
int i=0,id=0,kw=0,num=0,op=0;
char keys[32][10]={"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
main()


    {
     char ch,str[25],seps[15]=" \t\n,;(){}[]#\"<>",oper[]="!%^&*-+=~|.<>/?";
     int j;
     char fname[50];
     FILE *f1;
     //clrscr();
    printf("enter file path (drive:\\fold\\filename)\n");
    scanf("%s",fname);
    f1 = fopen(fname,"r");
    //f1 = fopen("Input","r");
     if(f1==NULL)


         {
          printf("file not found");
          exit(0);
         }
         while((ch=fgetc(f1))!=EOF)


             {
            for(j=0;j<=14;j++)


                {
                if(ch==oper[j])


                    {
                    printf("%c is an operator\n",ch);
                    op++;
                    str[i]='\0';
                    keyw(str);
                }
            }
            for(j=0;j<=14;j++)


                {
                if(i==-1)
                break;
                if(ch==seps[j])


                    {
                    if(ch=='#')


                        {
                        while(ch!='>')


                            {
                            printf("%c",ch);
                            ch=fgetc(f1);
                        }
                        printf("%c is a header file\n",ch);
                        i=-1;
                        break;
                    }
                    if(ch=='"')


                        {
                        do


                            {
                            ch=fgetc(f1);
                            printf("%c",ch);
                        }while(ch!='"');
                        printf("\b is an argument\n");
                        i=-1;
                        break;
                    }
                    str[i]='\0';
                    keyw(str);
                }
            }
            if(i!=-1)


                {
                str[i]=ch;
                i++;
            }
            else
            i=0;
             }
            printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers: %d\n",kw,id,op,num);
            //getch();
        }
        void keyw(char *p)


            {
            int k,flag=0;
            for(k=0;k<=31;k++)


                {
                if(strcmp(keys[k],p)==0)


                    {
                    printf("%s is a keyword\n",p);
                    kw++;
                    flag=1;
                    break;
                }
            }
            if(flag==0)


                {
                if(isdigit(p[0]))


                    {
                    printf("%s is a number\n",p);
                    num++;
                }
                else


                    {
                    //if(p[0]!=13&&p[0]!=10)
                    if(p[0]!='\0')


                        {
                        printf("%s is an identifier\n",p);
                        id++;
                    }
                }
            }
            i=-1;
        }
output

LEXICAL ANALYZER USING C
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void keyw(char *p);
int i=0,id=0,kw=0,num=0,op=0;
char keys[32][10]={"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
main()


    {
     char ch,str[25],seps[15]=" \t\n,;(){}[]#\"<>",oper[]="!%^&*-+=~|.<>/?";
     int j;
     char fname[50];
     FILE *f1;
     //clrscr();
    printf("enter file path (drive:\\fold\\filename)\n");
    scanf("%s",fname);
    f1 = fopen(fname,"r");
    //f1 = fopen("Input","r");
     if(f1==NULL)


         {
          printf("file not found");
          exit(0);
         }
         while((ch=fgetc(f1))!=EOF)


             {
            for(j=0;j<=14;j++)


                {
                if(ch==oper[j])


                    {
                    printf("%c is an operator\n",ch);
                    op++;
                    str[i]='\0';
                    keyw(str);
                }
            }
            for(j=0;j<=14;j++)


                {
                if(i==-1)
                break;
                if(ch==seps[j])


                    {
                    if(ch=='#')


                        {
                        while(ch!='>')


                            {
                            printf("%c",ch);
                            ch=fgetc(f1);
                        }
                        printf("%c is a header file\n",ch);
                        i=-1;
                        break;
                    }
                    if(ch=='"')


                        {
                        do


                            {
                            ch=fgetc(f1);
                            printf("%c",ch);
                        }while(ch!='"');
                        printf("\b is an argument\n");
                        i=-1;
                        break;
                    }
                    str[i]='\0';
                    keyw(str);
                }
            }
            if(i!=-1)


                {
                str[i]=ch;
                i++;
            }
            else
            i=0;
             }
            printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers: %d\n",kw,id,op,num);
            //getch();
        }
        void keyw(char *p)


            {
            int k,flag=0;
            for(k=0;k<=31;k++)


                {
                if(strcmp(keys[k],p)==0)


                    {
                    printf("%s is a keyword\n",p);
                    kw++;
                    flag=1;
                    break;
                }
            }
            if(flag==0)


                {
                if(isdigit(p[0]))


                    {
                    printf("%s is a number\n",p);
                    num++;
                }
                else


                    {
                    //if(p[0]!=13&&p[0]!=10)
                    if(p[0]!='\0')


                        {
                        printf("%s is an identifier\n",p);
                        id++;
                    }
                }
            }
            i=-1;
        }
output