Token Identification using Transition diagram

The following program uses transition diagram to identify the pre-defined tokens of C language. For valid token is will display the token type as well as state-table(traversal) and the states at which there is a failure. For invalid tokens it will simply print the states at which it has failed in different transition diagrams: Given below is a part of the transition diagram for pre-defined symbols: The states 34,36,38,40,42 and 44 are final states and will return "{",",",...",?" respectively

Here is the file of complete Transition diagram http://sdrv.ms/1at8wQ3



#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
int main(void)
{
char *str,ar[80];
char *start,*current,*next,*super;
char *ftest[45];
int *fail,iden_final[11],ope_final[7],sym_final[7];
int  count=0,n,len,i=0,key=TRUE,ide_len=0,state=0,choice;
int ide=TRUE,ide_t=TRUE,lit=TRUE,lit_t=TRUE,ope=TRUE,symb=TRUE,numb,negative=FALSE,j=0;
fail=(int *)malloc(44*sizeof(int));
for(i=0;i<45;i++)
{
fail[i]=FALSE;
ftest[i]=(char*)malloc(60*sizeof(char));
}
for(i=0;i<11;i++)
iden_final[i]=FALSE;
for(i=0;i<7;i++)
ope_final[i]=sym_final[i]=FALSE;
printf("\n Enter the maximum length of the statement:");
scanf(" %d", &n);
str=(char *)malloc( (n+1)*sizeof(char));
fflush(stdin);
printf("\n Enter the C statement:");
scanf("%[^\n]",str);
len=strlen(str);
if(len>n)
{
printf("\n Length of the statement is greater than the input length:");
exit(1);
}
super=str;
while(*super==' ')
super++;
while(*super !='\0' || *super =='\n')
{
start=super;
current=start;
next=current;
//Transistion diagram for Keywords int,if,for
switch(*current)
{
case 'i':
  //printf("\n>>>>>>>>%c",*current);
ar[0]=*current;
next +=1;
if(*next == ' ' || *next == '\0')
{
//printf("\n Failed at state 1:");
strcpy(ftest[1],"Failed at state 1:");
fail[1]=TRUE;
//ftest[strlen("Failed at state 1:")]='\0';
key=FALSE;
break;
}
current=next;
if(*current!='n' && *current !='f')
{
//printf("\n Failed at state 1:");
strcpy(ftest[1],"Failed at state 1:");
fail[1]=TRUE;
//ftest[strlen("Failed at state 1:")]='\0';
key=FALSE;
break;
}
ar[1]=*current;
 // printf("\n>>>>>n or f >>>%c",*current);
next +=1;
if(*next == ' ' || *next == '\0' || *current == 'f')
{
//   printf("\n In test loop:");
if(ar[1]!='f')
{
//printf("\n Failed at state 5:");
strcpy(ftest[5],"Failed at state 5:");
fail[5]=TRUE;
//ftest[strlen("Failed at state 5:")]='\0';
key=FALSE;
}
// printf("\n>>>>>>>>>>> [%c]",*next);
if(*next != ' ' && *next!='\0')
{
//printf("\n Failed at state 5:");
key=FALSE;
strcpy(ftest[5],"Failed at state 5:");
fail[5]=TRUE;
 // ftest[strlen("Failed at state 5:")]='\0';
break;
}
ar[2]='\0';
current=next;
if(key==TRUE)
iden_final[6]=TRUE;
printf("%s\t\t Keyword",ar);
break;
}
current=next;
if(*current!='t')
{
//printf("\n Failed at state 2:");
strcpy(ftest[2],"Failed at state 2:");
fail[2]=TRUE;
//ftest[strlen("Failed at state 2:")]='\0';
key=FALSE;
break;
}
ar[2]=*current;
//printf("\n>>>>>>>>%c",*current);
next +=1;
if(*next !=' ' && *next !='\0')
{
//printf("\n Failed at state 3:");
key=FALSE;
strcpy(ftest[3],"Failed at state 3:");
fail[3]=TRUE;
//ftest[strlen("Failed at state 3:")]='\0';
break;
}
current=next;
ar[3]='\0';
//printf("\nFFFFFFFF%c",*current);
iden_final[4]=TRUE;
printf("%s\t\t Keyword",ar);
break;
// CASE for
case 'f':
ar[0]=*current;
next +=1;
if(*next == ' ' || *next == '\0')
{
//printf("\n Failed at state 7:");
strcpy(ftest[7],"Failed at state 7:");
fail[7]=TRUE;
//ftest[strlen("Failed at state 7:")]='\0';
key=FALSE;
break;
}
current=next;
if(*current!='o')
{
//printf("\n Failed at state 7:");
strcpy(ftest[7],"Failed at state 7:");
fail[7]=TRUE;
//ftest[strlen("Failed at state 7:")]='\0';
key=FALSE;
break;
}
ar[1]=*current;
next +=1;
if(*next ==' ' && *next =='\0')
{
//printf("\n Failed at state 8:");
strcpy(ftest[8],"Failed at state 8:");
fail[8]=TRUE;
//ftest[strlen("Failed at state 8:")]='\0';
key=FALSE;
break;
}
current=next;
if(*current!='r')
{
//printf("\n Failed at state 8:");
strcpy(ftest[8],"Failed at state 8:");
fail[8]=TRUE;
//ftest[strlen("Failed at state 8:")]='\0';
key=FALSE;
break;
}
ar[2]=*current;
next +=1;
if(*next !=' ' && *next !='\0')
{
//printf("\n Failed at state 9:");
strcpy(ftest[9],"Failed at state 9:");
fail[9]=TRUE;
//ftest[strlen("Failed at state 9:")]='\0';
key=FALSE;
break;
}
current=next;
ar[3]='\0';
//printf("\nFFFFFFFF%c",*current);
iden_final[10]=TRUE;
printf("%s\t\t Keyword",ar);
break;
default:
//printf("\n Failure at state 0 in Keyword transistion:");
strcpy(ftest[0],"Failed at state 0:");
fail[0]=TRUE;
//ftest[strlen("Failed at state 0:")]='\0';
key=FALSE;
break;
}
// State traversal diagram
if(iden_final[6]==TRUE)
{
printf("\n i\t\t 0(s)---->1");
printf("\n f\t\t 1------->2");
printf("\n *D\t\t 5---->6(f)");
printf("\n");
}
if(iden_final[4]==TRUE)
{
printf("\n i\t\t 0(s)---->1");
printf("\n n\t\t 1------->2");
printf("\n t\t\t 2------->3");
printf("\n *D\t\t 3---->4(f)");
printf("\n");
}
 if(iden_final[10]==TRUE)
{
printf("\n f\t\t 0(s)---->7");
printf("\n 0\t\t 7------->8");
printf("\n r\t\t 8------->9");
printf("\n *D\t\t 9--->10(f)");
printf("\n");
}

// Transistion diagram for identifier
ide_len=0;
i=0;
if(key==FALSE)
{
state=0;
current=start;
while(*current!= ' ' && *current !='\0')
{
ar[i++]=*current;
current++;
}
ar[i]='\0';
current=start;
if( !(65 <= *current && *current <= 93 ) && !(97 <= *current && *current <= 122 )  )
{
//printf("\n Failed at state 11 in identifier transistion:");
strcpy(ftest[11],"Failed at state 11:");
fail[11]=TRUE;
//ftest[strlen("Failed at state 11:")]='\0';
ide_t=FALSE;
ide=FALSE;
}
current +=1;
next=current;
ide_len++;
while(*current!= ' ' && *current !='\0' && ide_t==TRUE)
{
if( (65 <= *current && *current <= 93 ) ||  ( 97 <= *current && *current <= 122)  || ( 48 <= *current && *current <= 57) || *current==95 )
{
ide_len++;
state++;
}
else
{
//printf("\n Failed at state 12:");
strcpy(ftest[1],"Failed at state 12:");
fail[12]=TRUE;
//ftest[strlen("Failed at state 12:")]='\0';
ide_t=FALSE;
ide=FALSE;
break;
}
current++;
}
if(ide_len>8 || ide_t==FALSE )
{ide=FALSE;}//printf("\n %s is Invalid identifier:",ar);
else
{
ide=TRUE;
printf("\n %s\t\t Identifier:",ar);
printf("\n %c\t\t11(s)------->12",ar[0]);
for(i=1;i<=state;i++)
printf("\n %c\t\t12------->12",ar[i]);
printf("\n *D\t\t12------->13");
printf("\n");
}

} // end of trans for iden
// Start of transisition for constant
i=0;
j=0;
state=0;
if(key==FALSE && ide==FALSE)
{
current=start;
while(*current!= ' ' && *current !='\0')
{
ar[i++]=*current;
current++;
}
ar[i]='\0';
current=start;
next=start;
if( !(48 <= *current && *current <= 57 ) )
{
//printf("\n Failed at state 14 in Literal transistion:");
strcpy(ftest[14],"Failed at state 14:");
fail[14]=TRUE;
//ftest[strlen("Failed at state 14:")]='\0';
//addddddd
lit_t=FALSE;
}
if(*current=='-')
negative=TRUE;
current +=1;
next=current;
ide_len++;
while(*current!= ' ' && *current !='\0' && lit_t==TRUE)
{
if((48 <= *current && *current <= 57 ))
{
state++;
}
else
{
//printf("\n Failed at state 15:");
strcpy(ftest[15],"Failed at state 15:");
fail[15]=TRUE;
//ftest[strlen("Failed at state 15:")]='\0';
if(*current!='.')
{
j++;
lit_t=FALSE;
}
else
lit_t=FALSE;
//break;
}
current++;
}
if(lit_t==FALSE )
{
if(negative==TRUE && lit_t==TRUE)
{
printf("\n %s\t\t Out of range:",ar);
lit=TRUE;
}
else
lit=FALSE;
}//printf("\n %s is Invalid identifier:",ar);
else
{
numb=atoi(ar);
if(numb <=0 || numb >999)
{
printf("\n %s\t\t Out of range:",ar);
lit=TRUE;
}
else {
lit=TRUE;
printf("\n %s\t\t Constant:",ar);
printf("\n %c\t\t14(s)------->15",ar[0]);
for(i=1;i<=state;i++)
printf("\n %c\t\t15------->15",ar[i]);
printf("\n *D\t\t15------->16");
printf("\n");

}
}
} // end of if for literal trans
//start of transistion of operators
i=0;
if(key==FALSE && lit==FALSE && ide==FALSE)// && negative == FALSE)
{
//printf("\n in OPERATORSSSSSSSSSSSSSSSSSS");
strcpy(ar,"");
current=start;
next=current;
ar[0]=*current;
//    printf("\n>>>>>>>>> %c",*current);
switch(*current)
{
case '+':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
ope=TRUE;
current=next;
ope_final[0]=TRUE;
}
else
{
//printf("\n Failed at state 18:");
strcpy(ftest[18],"Failed at state 18:");
fail[18]=TRUE;
//ftest[strlen("Failed at state 18:")]='\0';
ope=FALSE;
}
break;
case '-':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
ope=TRUE;
current=next;
ope_final[1]=TRUE;
}
else
{
//printf("\n Failed at state 20:");
if((48<= *next && *next <= 57))
{
//printf("\n Failed at state 20:  %c",*next);
strcpy(ftest[20],"Failed at state 20:");
fail[20]=FALSE;
//ftest[strlen("Failed at state 20:")]='\0';
ope=FALSE;
}
else
{
          printf("\n Failed at state 20:  %c",*next);
strcpy(ftest[20],"Failed at state 20:");
fail[20]=TRUE;
//ftest[strlen("Failed at state 20:")]='\0';
ope=FALSE;
}
}
break;
case '*':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
ope=TRUE;
current=next;
ope_final[2]=TRUE;
}
else
{
//printf("\n Failed at state 22:");
strcpy(ftest[22],"Failed at state 22:");
fail[22]=TRUE;
//ftest[strlen("Failed at state 22:")]='\0';
ope=FALSE;
}
break;
case '/':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
ope=TRUE;
current=next;
ope_final[3]=TRUE;
}
else
{
//printf("\n Failed at state 24:");
strcpy(ftest[24],"Failed at state 24:");
fail[24]=TRUE;
//ftest[strlen("Failed at state 24:")]='\0';
ope=FALSE;
}
break;
case '=':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
ope=TRUE;
current=next;
ope_final[4]=TRUE;
}
else
{
//printf("\n Failed at state 26:");
strcpy(ftest[26],"Failed at state 26:");
fail[26]=TRUE;
//ftest[strlen("Failed at state 26:")]='\0';
ope=FALSE;
}
break;
case '>':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
ope=TRUE;
current=next;
ope_final[5]=TRUE;
}
else
{
//printf("\n Failed at state 28:");
strcpy(ftest[28],"Failed at state 28:");
fail[28]=TRUE;
//ftest[strlen("Failed at state 28:")]='\0';
ope=FALSE;
}
break;
case '<':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
ope=TRUE;
current=next;
ope_final[6]=TRUE;
}
else
{
//printf("\n Failed at state 30:");
strcpy(ftest[30],"Failed at state 30:");
fail[30]=TRUE;
//ftest[strlen("Failed at state 30:")]='\0';
ope=FALSE;
}
break;
default:
ope=FALSE;
//printf("\n Failed at state 17 in operator transistion:");
strcpy(ftest[17],"Failed at state 17:");
fail[17]=TRUE;
//ftest[strlen("Failed at state 17:")]='\0';
break;
}// end of switch
if(ope==TRUE)
printf("\n %s\t\t Operator",ar);
else
{}//printf("\n %s\t\t is an Invalid Token:",ar);
}     // end of if for operator transisition
// State Table for operators
for(i=0;i<7;i++)
{
if(ope_final[i]==TRUE)
{
printf("\n %s\t\t 17(s)------>%d",ar,18+i*2);
printf("\n *D\t\t %d--------->%d(f)",18+i*2,(18+i*2)+1);
printf("\n");
}
}
// start of transistion for symbols
if(key==FALSE && lit==FALSE && ide==FALSE && ope==FALSE)// && negative == TRUE)
{
//printf("\n in SYMBOLSSSSSSSSSSSSSSSSS");
strcpy(ar,"");
current=start;
next=current;
ar[0]=*current;
//    printf("\n>>>>>>>>> %c",*current);
switch(*current)
{
case '{':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
symb=TRUE;
current=next;
sym_final[0]=TRUE;
}
else
{
//printf("\n Failed at state 33:");
strcpy(ftest[33],"Failed at state 33:");
fail[33]=TRUE;
//ftest[strlen("Failed at state 33:")]='\0';
symb=FALSE;
}
break;
case ',':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
ope=TRUE;
current=next;
sym_final[1]=TRUE;
}
else
{
//printf("\n Failed at state 35:");
strcpy(ftest[35],"Failed at state 35:");
fail[35]=TRUE;
//ftest[strlen("Failed at state 35:")]='\0';
symb=FALSE;
}
break;
case '(':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
symb=TRUE;
current=next;
sym_final[2]=TRUE;
}
else
{
//printf("\n Failed at state 37:");
strcpy(ftest[37],"Failed at state 37:");
fail[37]=TRUE;
//ftest[strlen("Failed at state 37:")]='\0';
symb=FALSE;
}
break;
case ')':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
symb=TRUE;
current=next;
sym_final[3]=TRUE;
}
else
{
//printf("\n Failed at state 39:");
strcpy(ftest[39],"Failed at state 39:");
fail[39]=TRUE;
//ftest[strlen("Failed at state 39:")]='\0';
ope=FALSE;
}
break;
case ';':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
symb=TRUE;
current=next;
sym_final[4]=TRUE;
}
else
{
//printf("\n Failed at state 41:");
strcpy(ftest[41],"Failed at state 41:");
fail[41]=TRUE;
//ftest[strlen("Failed at state 41:")]='\0';
symb=FALSE;
}
break;
case '?':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
symb=TRUE;
current=next;
sym_final[5]=TRUE;
}
else
{
//printf("\n Failed at state 43:");
strcpy(ftest[43],"Failed at state 43:");
fail[43]=TRUE;
//ftest[strlen("Failed at state 43:")]='\0';
symb=FALSE;
}
break;
case '<':
next +=1;
if(*next ==' ' || *next=='\0')
{
ar[1]='\0';
symb=TRUE;
current=next;
sym_final[6]=TRUE;
}
else
{
 // printf("\n Failed at state 30:");
symb=FALSE;
}
break;
default:
symb=FALSE;
//printf("\n Failed at state 32 in operator transistion:");
strcpy(ftest[32],"Failed at state 32:");
fail[32]=TRUE;
//ftest[strlen("Failed at state 32:")]='\0';
break;
}// end of switch
if(symb==TRUE)
printf("\n %s\t\t Symbol",ar);
else
{
if(atof(ar) || ar[0]=='0')
{
if(lit_t==FALSE && j>=1)
printf("\n %s\t\t is an Invalid Identifier:",ar);
else
printf("\n %s\t\t is an Invalid Constant:",ar);
}
else
printf("\n %s\t\t is an Invalid Token:",ar);
}
}              // end of if for symbol transistion
//printf("\ncurrent =[%c]",*current);
// State table for Symbols
for(i=0;i<7;i++)
{
if(sym_final[i]==TRUE)
{
printf("\n %s\t\t 32(s)------>%d",ar,33+i*2);
printf("\n *D\t\t %d--------->%d(f)",33+i*2,(33+i*2)+1);
printf("\n");
}
}
// Display failed states
printf("\n Want to see the failed states in different transistion 1/2:");
scanf("%d",&choice);
switch(choice)
{
case 1:
for(i=0;i<45;i++)
if(fail[i]==TRUE)
printf("\n%s",ftest[i]);
break;
case 2:
default:
break;
}
// variables resetting
for(i=0;i<11;i++)
iden_final[i]=FALSE;
for(i=0;i<7;i++)
ope_final[i]=sym_final[i]=FALSE;
for(i=0;i<45;i++)
fail[i]=FALSE;
key=TRUE;
ide_len=0;
ide=TRUE;
ide_t=TRUE;
lit=TRUE;
lit_t=TRUE;
ope=TRUE;
symb=TRUE;
negative=FALSE;
strcpy(ar,"");
printf("\n");
current=start;
next=current;
//printf("\n current =[%c]",*current);
do
{
if(*current=='\0' || *current=='\n')
break;

 // printf("\n current(loop) =[%c]",*current);
current++;
} while(*current!=' ');
do
{
if(*current=='\0' || *current=='\n')
break;

  // printf("\n current(loop) =[%c]",*current);
current++;
} while(*current==' ');
//printf("\n after current =[%c]",*current);
if(*current=='\0' || *current=='\n')
break;
next=current;
start=current;
super=current;
//printf("\n super =[%c]",*super);
if(*super=='\0' || *super =='\n' || *super ==' ')
break;
} // one token classification
return 0;
}

Newton's Backward Interpolation

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
void differenceTable(double **A,double **L,int ROW);
double result(double **A,double **L,double x,int ROW);
double factorial(int n);
FILE *fp;
int main(int argc, char *argv[])
{
double **A,*b,*xn,*xnplus1,*p,temp,x,**L,**U,lambda,error,t1=0.0;
int ROW,i,j,k,t=1,m=1,bo=1;
char ch;
if(argc==1)
{
printf("\n Enter the number of values:");
scanf("%d",&ROW);
printf("\n Enter the value at which value has to be aprroximated:");
scanf("%lf",&x);
A=(double **)malloc((ROW+1)*sizeof(double*));
L=(double **)malloc((ROW+1)*sizeof(double*));
U=(double **)malloc((ROW+1)*sizeof(double*));
for(i=0;i<=ROW;i++)
{
A[i]=(double *)malloc((ROW+1)*sizeof(double));
L[i]=(double *)malloc((ROW+1)*sizeof(double));
U[i]=(double *)malloc((ROW+1)*sizeof(double));
}
b=(double *)malloc((ROW+1)*sizeof(double));
p=(double *)malloc((ROW+1)*sizeof(double));
xn=(double *)malloc((ROW+1)*sizeof(double));
xnplus1=(double *)malloc((ROW+1)*sizeof(double));
for(i=1;i<=ROW;i++)
{
printf("\n Enter the value of X[%d]:",i);
scanf("%lf",&A[i][1]);
}
for(i=1;i<=ROW;i++)
{
printf("\n Enter the value of Y[%d]:",i);
scanf("%lf",&A[i][2]);
}

}
else if (argc==2)
{
fp=fopen(argv[1],"r");
if(fp==NULL)
{
printf("\n File not found, program will terminate:");
exit(0);
}
fscanf(fp,"%d",&ROW);
fscanf(fp,"%lf",&x);
A=(double **)malloc((ROW+1)*sizeof(double*));
L=(double **)malloc((ROW+1)*sizeof(double*));
U=(double **)malloc((ROW+1)*sizeof(double*));
for(i=0;i<=ROW;i++)
{
A[i]=(double *)malloc((ROW+1)*sizeof(double));
L[i]=(double *)malloc((ROW+1)*sizeof(double));
U[i]=(double *)malloc((ROW+1)*sizeof(double));
}
b=(double *)malloc((ROW+1)*sizeof(double));
p=(double *)malloc((ROW+1)*sizeof(double));
xn=(double *)malloc((ROW+1)*sizeof(double));
xnplus1=(double *)malloc((ROW+1)*sizeof(double));

while(!feof(fp))
{
for(i=1;i<=ROW;i++)
{
for(j=1;j<=2;j++)
{
fscanf(fp,"%lf ",&A[i][j]);
}

}
}
fclose(fp);
}
else
{
printf("\n Invalid Arguments,program will terminate:\n");
exit(0);
}
printf("\n         X          Y");
printf("\n------------------------------------------------------------------\n");
for(i=1;i<=ROW;i++)
{
for(j=1;j<=2;j++)
{

U[i][j]=A[i][j];
printf("   %+lf",U[i][j]);
}
printf("\n");
}
for(i=1;i<=ROW-1;i++)
{
for(j=ROW-i,t=1;j>=1;j--,t++)
{
L[t][i]=U[t+1][2]-U[t][2];
}
for(t=1;t<=ROW-i;t++)
U[t][2]=L[t][i];
}
differenceTable(A,L,ROW);
printf("\n Value at %+lf by Newton's Backward Interpolation formula is %+lf\n",x,result(A,L,x,ROW));
return 0;
}
double result(double **A,double **L,double x,int ROW)
{
int i,j,flag=1,t;

double h,value=0,p,tmp=1.0;
h=A[2][1]-A[1][1];
p=(A[ROW][1]-x)/h;
for(i=0,t=ROW+1;i<=ROW;i++,t--)
{
if(i==0)
value +=A[ROW][2];
else
{
for(j=1;j<=i;j++)
tmp=tmp*(p-j+1)*(-1);
tmp = tmp/factorial(i);
tmp = tmp*L[t-1][i];
value +=tmp;
}
tmp=1.0;
}
return value;
}
double factorial(int n)
{
 if(n<=1)
  return 1;
 else
  return n*factorial(n-1);
}
void differenceTable(double **A,double **L,int ROW)
{
int **position,*ap,j,m,i;
position=(int **)malloc((ROW+1)*sizeof(int*));
ap=(int *)malloc((ROW+1)*sizeof(int));
for(i=0;i<=ROW;i++)
position[i]=(int *)malloc((ROW+1)*sizeof(int));
int an,tmp;
tmp=ROW;
for(i=1;i<=ROW;i++)
{
an=1+(i-1)*2;
ap[i]=an;
for(j=1;j<=tmp;j++)
{
position[i][j]=an+(j-1)*4;
}
tmp--;
}
tmp=ROW;
tmp=ROW+(ROW-1)*3;
int *match,tmp1,l,*pos,flag,z,k;
match=(int *)malloc((ROW+1)*sizeof(int));
pos=(int *)malloc((ROW+1)*sizeof(int));
for(i=0;i<=ROW;i++)
{
match[i]=0;
pos[i]=0;
}

printf("\n-----------------------------Difference Table-----------------------------\n");
printf("\n X       Y");
for(i=1;i<=ROW-1;i++)
printf("      D_%d",i);
printf("\n--------------------------------------------------------------------------\n");
for(i=1;i<=tmp;i++)
{
tmp1=ROW;

for(l=1;l<=ROW;l++)
{
flag=0;
for(m=1;m<=tmp1;m++)
{
if(i==position[l][m])
{
flag=1;
match[l]=1;
pos[m]=position[l][m];
break;
}
} //inner for
if(flag==1)
{
for(k=1;k<=ROW;k++)
{
if(match[k]==0)
{
printf("");
}
else
{
if(k==1)
//printf("(%d,%d)+(%d,%d)|%d",(position[l][m]/4)+1,k,(position[l][m]/4)+1,k+1,i);
printf("%+2.2lf\t%+2.2lf",A[(position[l][m]/4)+1][k],A[(position[l][m]/4)+1][k+1]);
else
{
z=(position[l][m]-ap[k])/4+1;
//printf("\t\t(%d,%d)|%d",z,k-1,i);
printf("\t\t%+2.2lf",L[z][k-1]);
}

}
} //end of k-loop

} //end of flag==1

else
{printf(" ");}
tmp1--;
for(k=0;k<=ROW;k++)
{
pos[k]=0;
match[k]=0;
}
}

printf("\n");
}
printf("\n--------------------------------------------------------------------------\n");
}

Newton's Forward Interpolation : Numerical Analysis C Program

Newton's Forward Interpolation : Numerical Analysis C Program

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

void differenceTable(double **A,double **L,int ROW);

double result(double **A,double **L,double x,int ROW);

double factorial(int n);

FILE *fp;

int main(int argc, char *argv[]) {

double **A,*b,*xn,*xnplus1,*p,temp,x,**L,**U,lambda,error,t1=0.0;

int ROW,i,j,k,t=1,m=1,bo=1;

char ch;

if(argc==1) { 

    printf("\n Enter the number of values:");

    scanf("%d",&ROW);

    printf("\n Enter the value at which value has to be aprroximated:");

    scanf("%lf",&x);

    A=(double **)malloc((ROW+1)*sizeof(double*));

    L=(double **)malloc((ROW+1)*sizeof(double*));

    U=(double **)malloc((ROW+1)*sizeof(double*));

    for(i=0;i<=ROW;i++) {

        A[i]=(double *)malloc((ROW+1)*sizeof(double));

        L[i]=(double *)malloc((ROW+1)*sizeof(double));

        U[i]=(double *)malloc((ROW+1)*sizeof(double));

    }

 b=(double *)malloc((ROW+1)*sizeof(double));

 p=(double *)malloc((ROW+1)*sizeof(double));

 xn=(double *)malloc((ROW+1)*sizeof(double));

 xnplus1=(double *)malloc((ROW+1)*sizeof(double));

 for(i=1;i<=ROW;i++)  {

    printf("\n Enter the value of X[%d]:",i);

    scanf("%lf",&A[i][1]);

 }

 for(i=1;i<=ROW;i++) {

    printf("\n Enter the value of Y[%d]:",i);

    scanf("%lf",&A[i][2]);

 }

  

}

else if (argc==2) {

    fp=fopen(argv[1],"r");

    if(fp==NULL) {

        printf("\n File not found, program will terminate:");

        exit(0);

    }

    fscanf(fp,"%d",&ROW);

    fscanf(fp,"%lf",&x);

    A=(double **)malloc((ROW+1)*sizeof(double*));

    L=(double **)malloc((ROW+1)*sizeof(double*));

    U=(double **)malloc((ROW+1)*sizeof(double*));

    for(i=0;i<=ROW;i++) {

        A[i]=(double *)malloc((ROW+1)*sizeof(double));

        L[i]=(double *)malloc((ROW+1)*sizeof(double));

        U[i]=(double *)malloc((ROW+1)*sizeof(double));

    }

    b=(double *)malloc((ROW+1)*sizeof(double));

    p=(double *)malloc((ROW+1)*sizeof(double));

    xn=(double *)malloc((ROW+1)*sizeof(double));

    xnplus1=(double *)malloc((ROW+1)*sizeof(double));

    while(!feof(fp)) {

    for(i=1;i<=ROW;i++) {

        for(j=1;j<=2;j++) {

            fscanf(fp,"%lf ",&A[i][j]);

            }

        }

    }  

 fclose(fp);

 }

 else {

    printf("\n Invalid Arguments,program will terminate:\n");

    exit(0);

}

printf("\n         X          Y");

printf("\n------------------------------------------------------------------\n");

for(i=1;i<=ROW;i++) {

    for(j=1;j<=2;j++) {

        U[i][j]=A[i][j];

        printf("   %+lf",U[i][j]);

        }

    printf("\n");

}

for(i=1;i<=ROW-1;i++) {

    for(j=ROW-i,t=1;j>=1;j--,t++)  {

        L[t][i]=U[t+1][2]-U[t][2];

        }

 for(t=1;t<=ROW-i;t++)

    U[t][2]=L[t][i];

} 

differenceTable(A,L,ROW);

printf("\n Value at %+lf by Newton's Forward Interpolation formula is %+lf\n",x,result(A,L,x,ROW));

return 0;

}

double result(double **A,double **L,double x,int ROW) {

int i,j;

double h,value=0,p,tmp=1.0;

h=A[2][1]-A[1][1];

p=(x-A[1][1])/h;

for(i=0;i<ROW;i++){

    if(i==0)

    value +=A[1][2];

    else {

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

        tmp=tmp*(p-j+1);

        tmp = tmp/factorial(i);

        tmp = tmp*L[1][i];

        value +=tmp;

    }

    if(i==0)

        printf("%2.2lf ",A[1][2]);

    else

        printf("%2.2lf ",L[1][i]);

    tmp=1.0;

    }

    return value;

}

double factorial(int n) {

    if(n<=1)

        return 1;

    else

        return n*factorial(n-1);

}

void differenceTable(double **A,double **L,int ROW) {

    int **position,*ap,j,m,i;

    position=(int **)malloc((ROW+1)*sizeof(int*));

    ap=(int *)malloc((ROW+1)*sizeof(int));

    for(i=0;i<=ROW;i++)

        position[i]=(int *)malloc((ROW+1)*sizeof(int));

    int an,tmp; 

    tmp=ROW;

    for(i=1;i<=ROW;i++) {

        an=1+(i-1)*2;

        ap[i]=an;

        for(j=1;j<=tmp;j++)  {

            position[i][j]=an+(j-1)*4;

            }

        tmp--;

    }

    tmp=ROW;

    tmp=ROW+(ROW-1)*3;

    int *match,tmp1,l,*pos,flag,z,k;

    match=(int *)malloc((ROW+1)*sizeof(int));

    pos=(int *)malloc((ROW+1)*sizeof(int));

    for(i=0;i<=ROW;i++) {

        match[i]=0;

        pos[i]=0;

        }

printf("\n-----------------------------Difference Table-----------------------------\n");

printf("\n X       Y");

for(i=1;i<=ROW-1;i++)

    printf("      D^%d",i);

printf("\n--------------------------------------------------------------------------\n");

for(i=1;i<=tmp;i++) {

    tmp1=ROW;

     for(l=1;l<=ROW;l++) {

        flag=0;

        for(m=1;m<=tmp1;m++)  {

            if(i==position[l][m])   {

                flag=1;

                match[l]=1;

                pos[m]=position[l][m];

                break;

                }

            } //inner for

        if(flag==1)        {

            for(k=1;k<=ROW;k++)  {

                if(match[k]==0) {

                    printf("");

                }

        else  {

            if(k==1)

            //printf("(%d,%d)+(%d,%d)|%d",(position[l][m]/4)+1,k,(position[l][m]/4)+1,k+1,i);

                printf("%+2.2lf\t%+2.2lf",A[(position[l][m]/4)+1][k],A[(position[l][m]/4)+1][k+1]);

            else   {

                z=(position[l][m]-ap[k])/4+1;

                //printf("\t\t(%d,%d)|%d",z,k-1,i);

                printf("\t\t%+2.2lf",L[z][k-1]);

                }

            }

        } //end of k-loop     

    } //end of flag==1

    else

        {printf(" ");}

    tmp1--;

   for(k=0;k<=ROW;k++) {

        pos[k]=0;

        match[k]=0;

        }

    }

    printf("\n");

    }

printf("\n--------------------------------------------------------------------------\n");

}