# include <iostream.h> # include <stdlib.h> # include <string.h> # include <stdio.h> # include <conio.h> # include <math.h> const int max_size=13; int n=0; int top=-1; int choice=0; long double xn[max_size]={0}; long double px[max_size]={0}; long double dd_table[max_size][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 construct_dd_table( ); void show_dd_table( ); void compute_newtons_dd_interpolation_polynomial( ); void estimate_pnx( ); int main( ) { clrscr( ); textmode(C4350); show_screen( ); get_input( ); construct_dd_table( ); show_dd_table( ); compute_newtons_dd_interpolation_polynomial( ); estimate_pnx( ); return 0; } //-------------------------- show_screen( ) ---------------------------// void show_screen( ) { cprintf(\"\\n********************************************************************************\"); cprintf(\"*************- -************\"); cprintf(\"*------------- \"); textbackground(1); cprintf(\" Newton\'s Divided Difference Interpolation 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(3,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); cout<<\"Enter your choice : \"; 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) { dd_table[0][count_2]=evaluate_postfix_expression(xn[count_2]); gotoxy(43,(wherey( )-1)); cout<<dd_table[0][count_2]; } else { gotoxy(43,(wherey( )-1)); cin>>dd_table[0][count_2]; } if(choice) gotoxy(25,(wherey( )+2)); else gotoxy(25,(wherey( )+1)); } gotoxy(25,43); cout<<\"Press any key to continue...\"; getch( ); } //----------------------- construct_dd_table( ) -----------------------// void construct_dd_table( ) { for(int count_1=1;count_1<n;count_1++) { for(int count_2=count_1;count_2<n;count_2++) { long double fx1=dd_table[(count_1-1)][(count_2-1)]; long double fx2=dd_table[(count_1-1)][count_2]; long double x1=xn[(count_2-count_1)]; long double x2=xn[count_2]; dd_table[count_1][count_2]=((fx2-fx1)/(x2-x1)); } } } //-------------------------- show_dd_table( ) -------------------------// void show_dd_table( ) { clear_screen( ); gotoxy(4,10); cout<<\"Divided Difference Table :\"; gotoxy(4,11); cout<<\"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ\"; gotoxy(4,13); cout<<\"ÚÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\"; gotoxy(4,14); cout<<\"³ x ³ f(x) \"; gotoxy(4,15); cout<<\"ÃÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\"; gotoxy(4,16); cout<<\"³ ³ \"; int x_cord=4; int y_cord=17; for(int count_1=0;count_1<n;count_1++) { gotoxy(x_cord,y_cord); cout<<\"³ ³ \"; gotoxy(x_cord,(y_cord+1)); cout<<\"³ ³ \"; gotoxy((x_cord+2),y_cord); cout<<xn[count_1]; gotoxy((x_cord+11),y_cord); cout<<dd_table[0][count_1]; y_cord+=2; } gotoxy(x_cord,y_cord); cout<<\"ÀÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\"; x_cord=28; int count_2=0; for(int count_3=1;count_3<n;count_3++) { gotoxy(x_cord,13); cout<<\"ÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\"; gotoxy(x_cord,14); cout<<\"³\"; gotoxy(x_cord,15); cout<<\"ÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\"; gotoxy(x_cord,16); cout<<\"³\"; gotoxy(x_cord,y_cord); cout<<\"ÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\"; gotoxy((x_cord+6),14); cout<<count_3; if(count_3==1) cout<<\"st\"; else if(count_3==2) cout<<\"nd\"; else if(count_3==3) cout<<\"rd\"; else cout<<\"th\"; y_cord=17; for(int count_4=0;count_4<n;count_4++) { gotoxy(x_cord,y_cord); cout<<\"³\"; gotoxy(x_cord,(y_cord+1)); cout<<\"³\"; if(count_4>=count_3) { gotoxy((x_cord+2),(y_cord-count_3)); cout<<dd_table[count_3][count_4]; } y_cord+=2; } x_cord+=16; count_2++; if((count_2%3)==0 && count_3<(n-1)) { gotoxy(x_cord,13); cout<<\"ÂÄÄ\"; gotoxy(x_cord,14); cout<<\"³\"; gotoxy(x_cord,15); cout<<\"ÅÄÄ\"; gotoxy(x_cord,16); cout<<\"³\"; gotoxy(x_cord,y_cord); cout<<\"ÁÄÄ\"; y_cord=17; for(int count_5=0;count_5<n;count_5++) { gotoxy(x_cord,y_cord); cout<<\"³\"; gotoxy(x_cord,(y_cord+1)); cout<<\"³\"; y_cord+=2; } gotoxy(30,44); cout<<\"Press any key to continue...\"; getch( ); y_cord=13; x_cord=28; for(int count_6=0;count_6<=(n+2);count_6++) { gotoxy(x_cord,y_cord); cout<<\" \"; gotoxy(x_cord,(y_cord+1)); cout<<\" \"; y_cord+=2; } y_cord-=2; count_2=0; count_3--; } } gotoxy(x_cord,13); cout<<\"¿\"; gotoxy(x_cord,14); cout<<\"³\"; gotoxy(x_cord,16); cout<<\"³\"; y_cord=17; for(int count_6=0;count_6<n;count_6++) { gotoxy(x_cord,y_cord); cout<<\"³\"; gotoxy(x_cord,(y_cord+1)); cout<<\"³\"; y_cord+=2; } gotoxy(x_cord,15); cout<<\"\"; gotoxy(x_cord,y_cord); cout<<\"Ù\"; gotoxy(30,44); cout<<\"Press any key to continue...\"; getch( ); } //--------- compute_newtons_dd_interpolation_polynomial( ) ------------// void compute_newtons_dd_interpolation_polynomial( ) { for(int count_1=0;count_1<n;count_1++) xn[count_1]=(xn[count_1]*(-1)); px[0]=dd_table[0][0]; for(int count_2=1;count_2<n;count_2++) { long double fx[max_size]={0}; fx[0]=xn[0]; fx[1]=1; for(int count_3=0;count_3<(count_2-1);count_3++) { fx[(count_3+2)]=1; for(int count_4=(1+count_3);count_4>0;count_4--) { fx[count_4]*=xn[(count_3+1)]; fx[count_4]+=fx[(count_4-1)]; } fx[0]*=xn[(count_3+1)]; } for(int count_5=0;count_5<(count_2+1);count_5++) fx[count_5]*=dd_table[count_2][count_2]; for(int count_6=0;count_6<(count_2+1);count_6++) px[count_6]+=fx[count_6]; } } //---------------------------- estimate_pnx( ) ------------------------// void estimate_pnx( ) { clear_screen( ); gotoxy(6,10); cout<<\"Newton\'s Divided Difference Interpolation 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,40); cout<<\"Press <Esc> to exit, \'V\' to view D.D. Table again\"; gotoxy(25,42); cout<<\"or any other key to continue...\"; Choice=getch( ); if(int(Choice)!=27 && Choice!=\'v\' && Choice!=\'V\') { gotoxy(10,22); cout<<\" \"; gotoxy(10,26); cout<<\" \"; gotoxy(10,28); cout<<\" \"; gotoxy(10,30); cout<<\" \"; gotoxy(15,40); cout<<\" \"; gotoxy(25,42); cout<<\" \"; } else if(Choice==\'v\' || Choice==\'V\') { show_dd_table( ); estimate_pnx( ); } else if(int(Choice)==27) exit(0); } while(1); }