Insertion Sort using C++

Program Code:

#include<iostream.h>
#include<conio.h>
main()
{
int a[50],size;
char ch;
cout<<"Enter size of array\n";
cin>>size;
cout<<"Enter the order of sorting\n";
cout<<"Enter a for ascending or d for decending\n";
cin>>ch;
cout<<"Enter elements of array\n";
for(int i=0;i<size;i++)
{
cin>>a[i];
}
int t;
for(int i=1;i<=size;i++)
{
t=a[i];
for(int j=0;j<i;j++)
{
if(t<a[j])
{
for(int k=i;k>=j;k--)
{
a[k]=a[k-1];
}
a[j]=t;
break;

}
}
}
cout<<"The sorted array is\n";
if(ch=='a')
{
        for(int i=0;i<size;i++)
        {
cout<<a[i]<<"\t";
}
}
else if(ch=='d')
{
        for(int i=size-1;i>=0;i--)
{
cout<<a[i]<<"\t";
}
}
getch();
}

Output:

Read More

Bubble sort using C++

Program Code:


#include<iostream.h>
#include<conio.h>
main()
{
int a[50],size;
char ch;
cout<<"Enter size of array\n";
cin>>size;
cout<<"Enter the order of sorting\n";
cout<<"Enter a for ascending or d for decending\n";
cin>>ch;
cout<<"Enter elements of array\n";
for(int i=0;i<size;i++)
{
cin>>a[i];
}
for(int i=0;i<size;i++)
{
for(int j=0;j<size-i;j++)
{
if(a[j+1]<a[j])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
cout<<"The sorted array is\n";
if(ch=='a')
{
        for(int i=0;i<size;i++)
        {
cout<<a[i]<<"\t";
}
}
else if(ch=='d')
{
        for(int i=size-1;i>=0;i--)
{
cout<<a[i]<<"\t";
}
}
getch();
}

Output:

Read More

Selection sort using C++

Program Code:

#include<iostream.h>
#include<conio.h>
main()
{
int a[50],size;
char ch;
cout<<"Enter size of array\n";
cin>>size;
cout<<"Enter the order of sorting\n";
cout<<"Enter a for ascending or d for decending\n";
cin>>ch;
cout<<"Enter elements of array\n";
for(int i=0;i<size;i++)
{
cin>>a[i];
}
for(int i=0;i<size-1;i++)
{
for(int j=i+1;j<size;j++)
{
if(a[i]<a[j])
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
cout<<"The sorted array is\n";
if(ch=='d')
{
        for(int i=0;i<size;i++)
        {
cout<<a[i];
}
}
else if(ch=='a')
{
        for(int i=size-1;i>=0;i--)
{
cout<<a[i]<<"\t";
}
}
getch();
}

Output:

Read More

Binary Search using C++

Program Code:

#include<iostream.h>
#include<conio.h>
int binarySearch(int a[],int,int);

main()
{
int arr[50],size,index,target;
cout<<"Enter the size of array(max 50):\n";
cin>>size;
cout<<"Enter the elements of the array:\n";
for(int i=0;i<size;i++)
{
cin>>arr[i];
}
cout<<"Enter the element to be searched:\n";
cin>>target;
index=binarySearch(arr,size,target);
if(index==-1)
{
cout<<"Element is not present in the list\n";
}
else
{
cout<<"Element is present at index "<<index+1;
}

getch();
}
int binarySearch(int a[],int s,int t)
{
int beg,last,mid;
beg=0;
last=s-1;
while(beg<=last)
{
mid=(beg+last)/2;
if(a[mid]==t)
{
return mid;
}
else if(t>a[mid])
{
beg=mid+1;
}
else
{
last=mid-1;
}
}
return -1;
}

Output:

Read More

Linear Search using C++

Program Code:


#include<iostream.h>
#include<conio.h>
int linearSearch(int a[],int,int);

main()
{
int arr[50],size,index,target;
cout<<"Enter the size of array(max 50):\n";
cin>>size;
cout<<"Enter the elements of the array:\n";
for(int i=0;i<size;i++)
{
cin>>arr[i];
}
cout<<"Enter the element to be searched:\n";
cin>>target;
index=linearSearch(arr,size,target);
if(index==-1)
{
cout<<"Element is not present in the list\n";
}
else
{
cout<<"Element is present at index "<<index+1;
}

getch();
}
int linearSearch(int a[],int s,int t)
{
for(int i=0;i<s;i++)
{
if(a[i]==t)
{
return i;
}
}
return -1;
}

Output:

Read More

Intermediate Code Generation

Program to generate intermediate code of any given expression.
Program:

#include<iostream.h>
#include<conio.h>
#include<ctype.h>
main()
{
      int i,k,t,len,b,p,j,c=0,y,o;
      char exp[45],temp[8][50],A[8],stack[8][8];
      char op[10]={'+','*','-','/'};
      char sym[11]={'0','1','2','3','4','5','6','7','8','9'};t=0;j=0;
      cout<<"Enter an  expression\n";
      cin>>exp;
      len=strlen(exp);
      for(i=len;i>=1;i--)
      {
          if(isdigit(exp[i]))
          {
                            while(isdigit(exp[i]))
                            {
                                                 temp[t][i]=exp[i];
                                                 i--;
                                               
                            } exp[i+1]='q';
                            cout<<"After reduction the new expression is  ";
                            for(b=0;b<=i+1;b++)
                            {
                                              cout<<exp[b];
                            }cout<<i<<endl;
          }
          else if(isalpha(exp[i]))
          {
               while(isalpha(exp[i]))
                 {
                    temp[t][i]=exp[i];
                    i--;
                 } exp[i+1]='q';
               
                            cout<<"After reduction the new expression is  ";
                            for(b=0;b<=i+1;b++)
                            {
                                              cout<<exp[b];
                            }cout<<i<<endl;
          }                
         t++;
      }
                                               
      getch();                    
}
Output:

                                      

                                 
                                                                       
                                                                                               

Read More

Implementation of Lexical Analyzer

Program to implement lexical analyzer in c++.
Program:

#include<iostream.h>
#include<conio.h>
#include<ctype.h>
#include<string.h>
main()
{
      int i,j,k,f,len,t;
      char exp[100],word[12][12];
      char op[10]={'+','*','-','/'};
      char key[10][10]={"while","do","else","if"};
      cout<<"Enter the expression\n";
      cin>>exp;
      len=strlen(exp);t=0;
      for(i=0;i<len;i++)
      {
          j=0;f=0;
          if(isalpha(exp[i]))
          {
                            while(isalpha(exp[i])||isdigit(exp[i]))
                            {
                                        word[t][j]=exp[i];
                                        i++;j++;
                            }
                            word[t][j]='\0';
                            i--;
                            for(k=0;k<10;k++)
                            {
                                             if(word[t]==key[k])
                                             {
                                                                cout<<"The "<<word[t]<<" is keyword\n";
                                                                f=1;
                                                                break;
                                             }
                            }
                            if(f==0)
                            {
                                       cout<<"The "<<word[t]<<" is identifier\n";
                            }
          }
          else if(isdigit(exp[i]))
          {
                while(isdigit(exp[i]))
                            {
                                        word[t][j]=exp[i];
                                        i++;j++;
                            }
                            i--;
                            cout<<"The "<<word[t]<<" is constant\n";
          }
          else
          {
              cout<<"The "<<exp[i]<<" is operator\n";
          }
          t++;
      }
      getch();
}    

Output:

Read More

Leading Edges for non terminals

Program to find the leading edge for non terminals present in the grammar production.
Program Code:


#include<iostream.h>
#include<conio.h>
#include<string.h>
main()
{

int n,j,i,k,b;
char pr[10][10],lead[10],temp;
cout<<"Enter the number of production rules you want to enter\n";
cin>>n;
cout<<"Enter the production rules";
for(i=0;i<n;i++)
{
cin>>pr[i];
}int d=0;
for(i=0;i<n;i++)
{d=0;
               for(j=3;j<7;j++)
               {
                                if(islower(pr[i][j]))
                                {
                                                      lead[pr[i][0]]=pr[i][j];
                                                     d=1;
                                                      break;
                                }
                    }
                    if(d==0)
                    {
                   
                      if(lead[pr[i][j]]!='\0')
                      {
                                             lead[pr[i][0]]=lead[pr[i][3]];
                                             break;
                      }
                    }
                   
                       
   }for(i=0;i<n;i++)
    {
                    cout<<"leading["<<pr[i][0]<<"]="<<lead[pr[i][0]]<<endl;
    }    
   getch();
}
                                                   
                                                     

Output:

                                                    

                                                   
                                                     

Read More

Trailing Edges For Productions

Program to find the trailing edge for non terminals present in the grammar production.
Program Code:


#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
main()
{

int n,j,i,len,l;

char pr[10][10],trail[10];
cout<<"Enter the number of production rules you want to enter\n";
cin>>n;
cout<<"Enter the production rules";
for(i=0;i<n;i++)
{
cin>>pr[i];
}
for(i=0;i<n;i++)
{int d=0;
               for(j=strlen(pr[i]);j>2;j--)
               {
                                if(islower(pr[i][j]))
                                {
                                                      trail[pr[i][0]]=pr[i][j];
                                                      d=1;
                                                      break;
                                }
                     }
                   if(d==0)
                   { while(pr[i][j]!='\0')
                    {l=j;j++;}
                           
                       if(trail[pr[i][j]]!='\0')
                      {
                                             trail[pr[i][0]]=trail[pr[i][l]]
                                             ;
                                             break;
                      }
                    }
                   
                       
   }for(i=0;i<n;i++)
    {
                    cout<<"trailing["<<pr[i][0]<<"]="<<trail[pr[i][0]]<<endl;
    }    
   getch();
}
                                                   
                                                     

Output:

                                                  
                                                     

Read More

Dijkastra's Algorithm

Here is the program to find the shortest path between two nodes using Dijkastra algorithm

import java.io.*;

class MyDijkastra3
{
public static void main(String args[]) throws Exception

{

int n,i,j,tc,temp,current,source,destination,minimum;
int nodes[]=new int[20];
int cost[]=new int[10];
int distance[][]= new int[20][20];
tc=0;temp=0;int f=0;

DataInputStream d = new DataInputStream(System.in);

System.out.println("Enter the number of nodes(max 30)");


n =Integer.parseInt(d.readLine());
System.out.println("Enter the costs to each node(if there is no path between two nodes put distance -1");

for( i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{

System.out.println("Cost"+i+"-"+j+"-->");

distance[i][j] = Integer.parseInt(d.readLine());

}

}

System.out.println("Enter the source node");
source =Integer.parseInt(d.readLine());

System.out.println("Enter the destination node");
destination=Integer.parseInt(d.readLine());
current=source;
minimum=1000;
for( i=current;i<=n;i++)
{
for(j=1;j<=n;j++)
{ if((i==j )|| (distance[i][j]==-1))
                                                                    {continue;
                                                                     }
else if(minimum>=distance[i][j])
{
minimum= distance[i][j];
current=j;
}
if(current==destination)
{System.out.println("Complete");f=1;
break;

}

}tc=tc+minimum;
minimum=10000;
distance[i][current]=-1;
distance[current][i]=-1;

if(f==1)
{
break;
}

}
if((distance[source][destination]!=0)&&(distance[source][destination]!=-1))
{if(distance[source][destination]<tc)
tc=distance[source][destination];
}


                                  System.out.println("The total min cost from"+ source +"to"+ destination +"is:"+tc);

}}

Read More

Basics of C++

1)What are the different storage classes in C?
Ans=>C has three types of storage: automatic, static and allocated.
          Variable having block scope and without static specifier have
           automatic storage duration.
          Variables with block scope, and with static specifier have static scope.
          Global variables (i.e, file scope) with or without the static specifier also
           have static scope.
2) How are pointer variables initialized?
Ans=>Pointer variable are initialized by one of the following two ways
          Static memory allocation
          Dynamic memory allocation

Read More

Worst Fit Memory Management Scheme

worst fit memory management program in c++
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
class WFMM
{ int a[50],c,par,i,j,n,p[50],d[50],r,s,b,m,min,g;
 public:   
        void input();
        void output();
}X;
void WFMM::input()
{
 c=1000;
 r=c;
 cout<<"Total memory Available = 1000";
 cout<<"\nEnter the number of partition that you want in memory\t";
 cin>>par;
 cout<<"\nEnter the size of remaining partitions";
 cout<<"\n\nRemaining Memory=\t1000";
 for(i=0;i<par;i++)
 {
   if(r!=0)
   {
    cout<<"\n Partition "<<i+1<<"\t";
    cin>>s;
    r=r-s;
    a[i]=s;
    cout<<"\n Remaining Memory="<<r;
   }
 }
 cout<<"\n\nEnter the number of processes\t";
 cin>>n;
 cout<<"\nEnter the size of processes\n";
 for(i=0;i<n;i++)
 {
  cout<<"\nP["<<i+1<<"] =\t";
  cin>>p[i];
 }
}
void WFMM::output()
{
 for(i=0;i<n;i++)
 {min=0;
  for(j=0;j<n;j++)
  {
   if(p[i]<=a[j])
   {m=a[j]-p[i];
    if(m>min)
    {min=m;
     d[i]=j+1;
    }
   }
  }
  g=d[i]-1;
  a[g]=a[g]-p[i];
 }
 cout<<"\n\nThe Process allocation are as Follows\n";
 cout<<"\nProcess\tPartition";
 for(i=0;i<n;i++)
  cout<<"\n P["<<i+1<<"]\t "<<d[i];
}
  main()
{

 X.input();
 X.output();
 getch();
}

Read More

Best Fit Memory Management Scheme

We can also allocate memory locations to dofferent processes using best fit memory management scheme.Here is the code in C++
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
class BFMM
{ int a[50],c,par,i,j,n,p[50],d[50],r,s,b,m,min,g;
 public:   
        void input();
        void output();
}X;
void BFMM::input()
{
 c=1000;
 r=c;
 cout<<"Total memory Available = 1000";
 cout<<"\nEnter the number of partition that you want in memory\t";
 cin>>par;
 cout<<"\nEnter the size of remaining partitions";
 cout<<"\n\nRemaining Memory=\t1000";
 for(i=0;i<par;i++)
 {
   if(r!=0)
   {
    cout<<"\n Partition "<<i+1<<"\t";
    cin>>s;
    r=r-s;
    a[i]=s;
    cout<<"\n Remaining Memory="<<r;
   }
 }
 cout<<"\n\nEnter the number of processes\t";
 cin>>n;
 cout<<"\nEnter the size of processes\n";
 for(i=0;i<n;i++)
 {
  cout<<"\nP["<<i+1<<"] =\t";
  cin>>p[i];
 }
}
void BFMM::output()
{
 for(i=0;i<n;i++)
 {min=1000;
  for(j=0;j<n;j++)
  {
   if(p[i]<=a[j])
   {m=a[j]-p[i];
    if(m<min)
    {min=m;
     d[i]=j+1;
    }
   }
  }
  g=d[i]-1;
  a[g]=a[g]-p[i];
 }
 cout<<"\n\nThe Process allocation are as Follows\n";
 cout<<"\nProcess\tPartition";
 for(i=0;i<n;i++)
  cout<<"\n P["<<i+1<<"]\t "<<d[i];
}
  main()
{

 X.input();
 X.output();
 getch();
}

Read More

First Fit Memory Management

we can use first fit memory management scheme to allocate memory space to different processes.Here is the program in c++
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
class FFMM
{ int a[50],c,par,i,j,n,p[50],d[50],e[50],r,s,b;
 public:   
        void input();
        void output();
}X;
void FFMM::input()
{
 c=1000;
 r=c;
 cout<<"Total memory Available = 1000";
 cout<<"\nEnter the number of partition that you want in memory\t";
 cin>>par;
 cout<<"\nEnter the size of remaining partitions";
 cout<<"\n\nRemaining Memory=\t1000";
 for(i=0;i<par;i++)
 {
   if(r!=0)
   {
    cout<<"\n Partition "<<i+1<<"\t";
    cin>>s;
    r=r-s;
    a[i]=s;
    cout<<"\n Remaining Memory=\t"<<r;
   }
 }
 cout<<"\n\nEnter the number of processes\t";
 cin>>n;
 cout<<"\nEnter the size of processes\n";
 for(i=0;i<n;i++)
 {
  cout<<"\nP["<<i+1<<"] =\t";
  cin>>p[i];
 }
}
void FFMM::output()
{
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  {
   if(p[i]<=a[j])
   {
    d[i]=j+1;
    a[j]=a[j]-p[i];
    break;
   }
  }
 }
 cout<<"\n\nThe Process allocation are as Follows\n";
 cout<<"\nProcess\tPartition";
 for(i=0;i<n;i++)
  cout<<"\n P["<<i+1<<"]\t "<<d[i];
}
  main()
{

 X.input();
 X.output();
 getch();
}

Read More