# Program to construct Lagrangess Interpolation Formula from the given distinct data points.

``` # include <iostream.h>
# include   <stdlib.h>
# include   <string.h>
# include    <stdio.h>
# include    <conio.h>
# include     <math.h>

const int max_size=12;

int n=0;
int top=-1;
int choice=0;

long double xn[max_size]={0};
long double fx[max_size]={0};
long double px[max_size]={0};

char Non_linear_equation[100]={NULL};
char Stack[30][30]={NULL};
char Postfix_expression[30][30]={NULL};

void push(const char *);
void convert_infix_expression_to_postfix_expression(const char *);

const char* pop( );
const long double evaluate_postfix_expression(const long double);

void show_screen( );
void clear_screen( );
void get_input( );
void compute_lagranges_interpolation_polynomial( );
void estimate_pnx( );

int main( )
{
clrscr( );
textmode(C4350);

show_screen( );
get_input( );
compute_lagranges_interpolation_polynomial( );
estimate_pnx( );

return 0;
}

//--------------------------  show_screen( )  ---------------------------//

void show_screen( )
{
cprintf(\"\\n********************************************************************************\");
cprintf(\"*****************************-                      -***************************\");
cprintf(\"*----------------------------- \");

textbackground(1);
cprintf(\" Lagrange\'s Formula \");
textbackground(8);

cprintf(\" ---------------------------*\");
cprintf(\"*-***************************-                      -*************************-*\");
cprintf(\"*-****************************************************************************-*\");

for(int count=0;count<42;count++)
cprintf(\"*-*                                                                          *-*\");

gotoxy(1,46);
cprintf(\"*-****************************************************************************-*\");
cprintf(\"*------------------------------------------------------------------------------*\");
cprintf(\"********************************************************************************\");

gotoxy(1,2);
}

//-------------------------  clear_screen( )  ---------------------------//

void clear_screen( )
{
for(int count=0;count<37;count++)
{
gotoxy(5,8+count);
cout<<\"                                                                        \";
}

gotoxy(1,2);
}

//--------------------------  push(const char*)  ------------------------//

void push(const char* Operand)
{
if(top==(max_size-1))
{
cout<<\"Error : Stack is full.\"<<endl;
cout<<\"\\n        Press any key to exit.\";

getch( );
exit(0);
}

else
{
top++;
strcpy(Stack[top],Operand);
}
}

//------------------------------  pop( )  -------------------------------//

const char* pop( )
{
char Operand[40]={NULL};

if(top==-1)
{
cout<<\"Error : Stack is empty.\"<<endl;
cout<<\"\\n        Press any key to exit.\";

getch( );
exit(0);
}

else
{
strcpy(Operand,Stack[top]);
strset(Stack[top],NULL);
top--;
}

return Operand;
}

//----  convert_infix_expression_to_postfix_expression(const char*)  ----//

void convert_infix_expression_to_postfix_expression(const char* Expression)
{
char Infix_expression[100]={NULL};
char Symbol_scanned[30]={NULL};

push(\"(\");
strcpy(Infix_expression,Expression);
strcat(Infix_expression,\"+0)\");

int flag=0;
int count_1=0;
int count_2=0;
int equation_length=strlen(Infix_expression);

if(Infix_expression[0]==\'(\')
flag=1;

do
{
strset(Symbol_scanned,NULL);

if(flag==0)
{
int count_3=0;

do
{
Symbol_scanned[count_3]=Infix_expression[count_1];

count_1++;
count_3++;
}
while(count_1<=equation_length &&
Infix_expression[count_1]!=\'(\' &&
Infix_expression[count_1]!=\'+\' &&
Infix_expression[count_1]!=\'-\' &&
Infix_expression[count_1]!=\'*\' &&
Infix_expression[count_1]!=\'/\' &&
Infix_expression[count_1]!=\'^\' &&
Infix_expression[count_1]!=\')\');

flag=1;
}

else if(flag==1)
{
Symbol_scanned[0]=Infix_expression[count_1];

count_1++;

if(Infix_expression[count_1]!=\'(\' &&
Infix_expression[count_1]!=\'^\' &&
Infix_expression[count_1]!=\'*\' &&
Infix_expression[count_1]!=\'/\' &&
Infix_expression[count_1]!=\'+\' &&
Infix_expression[count_1]!=\'-\' &&
Infix_expression[count_1]!=\')\')
flag=0;

if(Infix_expression[count_1-1]==\'(\' &&
(Infix_expression[count_1]==\'-\' ||
Infix_expression[count_1]==\'+\'))
flag=0;
}

if(strcmp(Symbol_scanned,\"(\")==0)
push(\"(\");

else if(strcmp(Symbol_scanned,\")\")==0)
{
while(strcmp(Stack[top],\"(\")!=0)
{
strcpy(Postfix_expression[count_2],pop( ));

count_2++;
}

pop( );
}

else if(strcmp(Symbol_scanned,\"^\")==0 ||
strcmp(Symbol_scanned,\"+\")==0 ||
strcmp(Symbol_scanned,\"-\")==0 ||
strcmp(Symbol_scanned,\"*\")==0 ||
strcmp(Symbol_scanned,\"/\")==0)
{
if(strcmp(Symbol_scanned,\"^\")==0)
{  }

else if(strcmp(Symbol_scanned,\"*\")==0 ||
strcmp(Symbol_scanned,\"/\")==0)
{
while(strcmp(Stack[top],\"^\")==0 ||
strcmp(Stack[top],\"*\")==0 ||
strcmp(Stack[top],\"/\")==0)
{
strcpy(Postfix_expression[count_2],pop( ));

count_2++;
}
}

else if(strcmp(Symbol_scanned,\"+\")==0 ||
strcmp(Symbol_scanned,\"-\")==0)
{
while(strcmp(Stack[top],\"(\")!=0)
{
strcpy(Postfix_expression[count_2],pop( ));

count_2++;
}
}

push(Symbol_scanned);
}

else
{
strcat(Postfix_expression[count_2],Symbol_scanned);

count_2++;
}
}
while(strcmp(Stack[top],NULL)!=0);

strcat(Postfix_expression[count_2],\"=\");
count_2++;
}

//----------  evaluate_postfix_expression(const long double)  -----------//

const long double evaluate_postfix_expression(const long double x)
{
long double function_value=0;

int count_1=-1;

char Symbol_scanned[30]={NULL};

do
{
count_1++;

strcpy(Symbol_scanned,Postfix_expression[count_1]);

if(strcmp(Symbol_scanned,\"^\")==0 ||
strcmp(Symbol_scanned,\"*\")==0 ||
strcmp(Symbol_scanned,\"/\")==0 ||
strcmp(Symbol_scanned,\"+\")==0 ||
strcmp(Symbol_scanned,\"-\")==0)

{
char Result[30]={NULL};
char Operand[2][30]={NULL};

strcpy(Operand[0],pop( ));
strcpy(Operand[1],pop( ));

long double operand[2]={0};
long double result=0;

char *endptr;

for(int count_2=0;count_2<2;count_2++)
{
int flag=0;

if(Operand[count_2][0]==\'-\')
{
int length=strlen(Operand[count_2]);

for(int count_3=0;count_3<(length-1);count_3++)
Operand[count_2][count_3]=Operand[count_2][(count_3+1)];

Operand[count_2][count_3]=NULL;

flag=1;
}

if(strcmp(Operand[count_2],\"x\")==0)
operand[count_2]=x;

else if(strcmp(Operand[count_2],\"e\")==0)
operand[count_2]=2.718282;

else if(strcmp(Operand[count_2],\"sinx\")==0)
operand[count_2]=sinl(x);

else if(strcmp(Operand[count_2],\"cosx\")==0)
operand[count_2]=cosl(x);

else if(strcmp(Operand[count_2],\"tanx\")==0)
operand[count_2]=tanl(x);

else if(strcmp(Operand[count_2],\"lnx\")==0)
operand[count_2]=logl(x);

else if(strcmp(Operand[count_2],\"logx\")==0)
operand[count_2]=log10l(x);

else
operand[count_2]=strtod(Operand[count_2],&endptr);

if(flag)
operand[count_2]*=-1;
}

switch(Symbol_scanned[0])
{
case \'^\' : result=powl(operand[1],operand[0]);
break;

case \'*\' : result=operand[1]*operand[0];
break;

case \'/\' : result=operand[1]/operand[0];
break;

case \'+\' : result=operand[1]+operand[0];
break;

case \'-\' : result=operand[1]-operand[0];
break;
}

gcvt(result,25,Result);

push(Result);
}

else if(strcmp(Symbol_scanned,\"=\")!=0)
push(Symbol_scanned);
}
while(strcmp(Symbol_scanned,\"=\")!=0);

char Function_value[30]={NULL};
char *endptr;

strcpy(Function_value,pop( ));
function_value=strtod(Function_value,&endptr);

return function_value;
}

//-----------------------------  get_input( )  --------------------------//

void get_input( )
{
do
{
clear_screen( );

gotoxy(6,9);
cout<<\"Number of Distinct Data Points :\";

gotoxy(6,10);
cout<<\"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ\";

gotoxy(27,13);
cout<<\"[ min. n = 2  |  max. n = 12 ]\";

gotoxy(6,12);
cout<<\"Enter the max. number of distinct data points = n = \";

cin>>n;

if(n<2 || n>12)
{
gotoxy(12,25);
cout<<\"Error : Wrong Input. Press <Esc> to exit or any other key\";

gotoxy(12,26);
cout<<\"        to try again.\";

n=int(getche( ));

if(n==27)
exit(0);
}
}
while(n<2 || n>12);

gotoxy(6,19);
cout<<\"Input Mode :\";

gotoxy(6,20);
cout<<\"ÍÍÍÍÍÍÍÍÍÍÍÍ\";

gotoxy(8,23);
cout<<\"Press : \";

gotoxy(10,25);
cout<<\"- \'Y\' or <Enter> to enter function\";

gotoxy(10,27);
cout<<\"- \'N\' or <Any other key> to enter values of the function\";

gotoxy(8,30);

char Choice=NULL;

Choice=getch( );

if(Choice==\'y\' || Choice==\'Y\' || int(Choice)==13)
{
choice=1;

gotoxy(28,30);
cout<<\"Y\";
}

else
{
gotoxy(28,30);
cout<<\"N\";
}

gotoxy(25,43);
cout<<\"Press any key to continue...\";

getch( );

if(choice)
{
clear_screen( );

gotoxy(6,11);
cout<<\"Non-Linear Function :\";

gotoxy(6,12);
cout<<\"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ\";

gotoxy(6,37);
cout<<\"Note : Write the function with proper Braces ( ) e.g; 2x+3 as (2*x)+3\";

gotoxy(6,40);
cout<<\"Available Operators  :  ^ (raised to power) , * , / , + , -\";

gotoxy(6,42);
cout<<\"Available Operands   :  x , e , sinx , cosx , tanx , lnx , logx ,\";

gotoxy(6,44);
cout<<\"                        n = any number\";

gotoxy(6,14);
cout<<\"Enter the Function : f(x) = \";

cin>>Non_linear_equation;

convert_infix_expression_to_postfix_expression(Non_linear_equation);
}

clear_screen( );

gotoxy(6,9);
cout<<\"Data Points & Values of Function :\";

gotoxy(6,10);
cout<<\"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ\";

gotoxy(25,12);
cout<<\"ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\";

gotoxy(25,13);
cout<<\"³       x       ³     f(x)      ³\";

gotoxy(25,14);
cout<<\"ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\";

gotoxy(25,15);
cout<<\"³               ³               ³\";

for(int count_1=0;count_1<n;count_1++)
{
gotoxy(25,(wherey( )+1));
cout<<\"³               ³               ³\";

gotoxy(25,(wherey( )+1));
cout<<\"³               ³               ³\";
}

gotoxy(25,(wherey( )+1));
cout<<\"ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\";

gotoxy(25,16);

for(int count_2=0;count_2<n;count_2++)
{
gotoxy(27,wherey( ));
cin>>xn[count_2];

if(choice)
{
fx[count_2]=evaluate_postfix_expression(xn[count_2]);

gotoxy(43,(wherey( )-1));
cout<<fx[count_2];
}

else
{
gotoxy(43,(wherey( )-1));
cin>>fx[count_2];
}

if(choice)
gotoxy(25,(wherey( )+2));

else
gotoxy(25,(wherey( )+1));
}

gotoxy(25,43);
cout<<\"Press any key to continue...\";

getch( );
}

//----------  compute_lagranges_interpolation_polynomial( )  ------------//

void compute_lagranges_interpolation_polynomial( )
{
for(int count_1=0;count_1<n;count_1++)
xn[count_1]=(xn[count_1]*(-1));

long double numerator[max_size][max_size]={0};
long double x[max_size]={0};

for(int count_2=0;count_2<n;count_2++)
{
for(int count_3=0;count_3<(n-1);count_3++)
{
if(count_3<count_2)
x[count_3]=xn[count_3];

else if(count_3>=count_2)
x[count_3]=xn[(count_3+1)];
}

numerator[count_2][0]=x[0];
numerator[count_2][1]=1;

for(int count_4=0;count_4<(n-2);count_4++)
{
numerator[count_2][(2+count_4)]=1;

for(int count_5=(1+count_4);count_5>0;count_5--)
{
numerator[count_2][count_5]*=x[(count_4+1)];

numerator[count_2][count_5]+=
numerator[count_2][(count_5-1)];
}

numerator[count_2][0]*=x[(count_4+1)];
}
}

for(int count_6=0;count_6<n;count_6++)
{
for(int count_7=0;count_7<n;count_7++)
numerator[count_6][count_7]*=fx[count_6];
}

long double denominator[max_size]={0};

for(int count_8=0;count_8<n;count_8++)
{
denominator[count_8]=1;

for(int count_9=0;count_9<n;count_9++)
{
if(count_8!=count_9)
denominator[count_8]*=(-1*(xn[count_8]-xn[count_9]));
}
}

long double equation[max_size][max_size]={0};

for(int count_10=0;count_10<n;count_10++)
{
for(int count_11=0;count_11<n;count_11++)
equation[count_10][count_11]=
(numerator[count_10][count_11]/denominator[count_10]);
}

for(int count_12=0;count_12<n;count_12++)
{
for(int count_13=0;count_13<n;count_13++)
px[count_12]+=equation[count_13][count_12];
}
}

//----------------------------  estimate_pnx( )  ------------------------//

void estimate_pnx( )
{
clear_screen( );

gotoxy(6,10);
cout<<\"Lagrange\'s Formula :\";

gotoxy(6,11);
cout<<\"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ\";

gotoxy(10,13);
cout<<\"P\"<<(n-1)<<\"(x)  =  \";

for(int count_1=(n-1);count_1>=0;count_1--)
{
if(count_1==(n-1) && n>2)
cout<<px[count_1]<<\" x\"<<count_1;

else if(count_1>1)
cout<<fabs(px[count_1])<<\" x\"<<count_1;

else if(count_1==1)
cout<<fabs(px[count_1])<<\" x\";

else if(count_1==0)
cout<<fabs(px[count_1]);

if(wherex( )>=70)
gotoxy(30,(wherey( )+2));

if(count_1>0)
{
if(px[(count_1-1)]>0)
cout<<\"  +  \";

else
cout<<\"  -  \";
}

if(wherex( )>=70)
gotoxy(30,(wherey( )+2));
}

gotoxy(6,19);
cout<<\"Estimation of Pn(x) :\";

gotoxy(6,20);
cout<<\"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ\";

char Choice=NULL;

long double x=0;
long double pnx=0;

do
{
Choice=NULL;

x=0;
pnx=0;

gotoxy(10,22);
cout<<\"Enter the value of x = \";
cin>>x;

pnx=px[0];
pnx+=(px[1]*x);

for(int count_2=2;count_2<n;count_2++)
{
long double temp=x;

for(int count_3=1;count_3<count_2;count_3++)
temp*=x;

pnx+=(px[count_2]*temp);
}

gotoxy(10,26);
cout<<\"The Estimated value of P\"<<(n-1)<<\"(\"<<x<<\")  =  \"<<pnx;

if(choice)
{
long double fx=0;

fx=evaluate_postfix_expression(x);

gotoxy(10,28);
cout<<\"The Actual value of f\"<<\"(\"<<x<<\")  =  \"<<fx;

gotoxy(10,30);
cout<<\"Absolute Error = E(abs) =  \"<<fabs((fx-pnx));
}

gotoxy(15,42);
cout<<\"Press <Esc> to exit or any other key to continue...\";

Choice=getch( );

if(int(Choice)!=27)
{
gotoxy(10,22);
cout<<\"                                                    \";

gotoxy(10,26);
cout<<\"                                                    \";

gotoxy(10,28);
cout<<\"                                                    \";

gotoxy(10,30);
cout<<\"                                                    \";

gotoxy(15,42);
cout<<\"                                                    \";
}
}
while(int(Choice)!=27);

gotoxy(1,2);
}
```