Program to construct Newtons Divided Difference Interpolation Formula from the given distinct data points and estimate the value of the function

 # 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);
    }