/*************************************************************************//*************************************************************************      A C++ Program to read a Non-Linear equation in one variable, then      evaluate it using Bisection Method and display its kD accurate root.  *************************************************************************//*************************************************************************/

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

 constint max_size=30;

 int top=-1;
 int accuracy=0;
 int iterations=0;

 longdouble a=0;
 longdouble b=0;
 longdouble x=0;

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

 /*************************************************************************//*************************************************************************///-----------------------  Function Prototypes  -------------------------///*************************************************************************//*************************************************************************/void push(constchar *);
 void convert_infix_expression_to_postfix_expression(constchar *);

 constchar* pop( );
 constlongdouble evaluate_postfix_expression(constlongdouble);
 constint calculate_number_of_iterations_for_kd_accuracy( );

 void show_screen( );
 void clear_screen( );
 void get_input_non_linear_equation( );
 void apply_bisection_method( );
 void show_result( );

 /*************************************************************************//*************************************************************************///------------------------------  main( )  ------------------------------///*************************************************************************//*************************************************************************/int main( )
    {
       clrscr( );
       textmode(C4350);

       show_screen( );
       get_input_non_linear_equation( );
       apply_bisection_method( );
       show_result( );

       getch( );
       return 0;
    }

 /*************************************************************************//*************************************************************************///----------------------  Function Definitions  -------------------------///*************************************************************************//*************************************************************************//*************************************************************************///--------------------------  push(const char*)  ------------------------///*************************************************************************/void push(constchar* 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( )  -------------------------------///*************************************************************************/constchar* 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(constchar* 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;
        }

         elseif(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("(");

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

             count_2++;
              }

           pop( );
        }

         elseif(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)
              {  }

           elseif(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++;
                }
              }

           elseif(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)  -----------///*************************************************************************/constlongdouble evaluate_postfix_expression(constlongdouble x)
    {
       longdouble 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( ));

           longdouble operand[2]={0};
           longdouble 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;

             elseif(strcmp(Operand[count_2],"e")==0)
                operand[count_2]=2.718282;

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

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

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

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

             elseif(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);
        }

         elseif(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;
    }

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

       textbackground(1);
       cprintf(" Bisection Method ");
       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);
    }

 /*************************************************************************///------------------- get_input_non_linear_equation( )  -----------------///*************************************************************************/void get_input_non_linear_equation( )
    {
       gotoxy(4,11);
       cout<<"Non-Linear Equation with One Variable:";

       gotoxy(4,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(4,14);
       cout<<"Enter the Function with variabel x = f(x) = ";
       cin>>Non_linear_equation;

       gotoxy(4,19);
       cout<<"Interval [a,b] where the root x lies :";

       gotoxy(4,20);
       cout<<"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ";

       gotoxy(4,22);
       cout<<"Enter the value of a  =  ";
       cin>>a;

       gotoxy(4,24);
       cout<<"Enter the value of b  =  ";
       cin>>b;

       gotoxy(4,28);
       cout<<"Enter the number of accuracy required = k =  ";
       cin>>accuracy;

       gotoxy(1,2);
    }

 /*************************************************************************///---------  calculate_number_of_iterations_for_kd_accuracy( )  ---------///*************************************************************************/constint calculate_number_of_iterations_for_kd_accuracy( )
    {
       longdouble iterations=0;

       iterations=((log10l(2)+log10l(b-a)+accuracy)/log10l(2));

       return ceill(iterations);
    }

 /*************************************************************************///---------------------  apply_bisection_method( )  ---------------------///*************************************************************************/void apply_bisection_method( )
    {
       clear_screen( );

       gotoxy(4,10);
       cout<<"Solution :";

       gotoxy(4,11);
       cout<<"ÍÍÍÍÍÍÍÍÍÍ";

       convert_infix_expression_to_postfix_expression(Non_linear_equation);

       int k=calculate_number_of_iterations_for_kd_accuracy( );

       iterations=k;

       gotoxy(4,13);
       cout<<"ÚÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄ¿";

       gotoxy(4,14);
       cout<<"³n ³      a      ³     Xm      ³      b      ³    f(Xm)    ³  Accuracy   ³";

       gotoxy(4,15);
       cout<<"ÃÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄ´";

       gotoxy(4,16);
       cout<<"³  ³             ³             ³             ³             ³             ³";

       longdouble a=::a;
       longdouble b=::b;
       longdouble old_x=0;
       longdouble new_x=x;
       longdouble fx=0;
       longdouble fa=0;

       int x_cord=4;
       int y_cord=17;

       for(int count_1=1;count_1<=k;count_1++)
      {
         gotoxy(x_cord,y_cord);
         cout<<"³  ³             ³             ³             ³             ³             ³";

         gotoxy(x_cord,(y_cord+1));
         cout<<"³  ³             ³             ³             ³             ³             ³";

         old_x=new_x;
         new_x=((a+b)/2);

         gotoxy((x_cord+1),y_cord);
         cout<<count_1;

         gotoxy((x_cord+4),y_cord);
         cout<<a;

         gotoxy((x_cord+18),y_cord);
         cout<<new_x;

         gotoxy((x_cord+32),y_cord);
         cout<<b;

         fx=evaluate_postfix_expression(new_x);
         fa=evaluate_postfix_expression(a);

         gotoxy((x_cord+46),y_cord);
         cout<<fx;

         gotoxy((x_cord+60),y_cord);
         cout<<(new_x-old_x);

         if(fx==0)
        break;

         elseif((fa*fx)<0)
        b=new_x;

         else
        a=new_x;

         y_cord+=2;

         if((count_1%12)==0 && count_1<k)
        {
           y_cord=17;

           gotoxy(30,44);
           cout<<"Press any key to continue...";
           getch( );

           for(int count_2=1;count_2<25;count_2++)
              {
             gotoxy(3,(16+count_2));
             cout<<"                                                                            ";
              }
        }
      }

       gotoxy(x_cord,y_cord);
       cout<<"ÀÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÙ";

       x=new_x;

       gotoxy(30,44);
       cout<<"Press any key to continue...";
       getch( );
    }

 /*************************************************************************///---------------------------  show_result( )  --------------------------///*************************************************************************/void show_result( )
    {
       clear_screen( );

       gotoxy(6,10);
       cout<<"Function of Non-Linear Equation :";

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

       gotoxy(10,13);
       cout<<"f(x)  =  "<<Non_linear_equation;

       gotoxy(6,17);
       cout<<"Interval [a,b]  =  [ "<<a<<" , "<<b<<" ]";

       gotoxy(6,19);
       cout<<"Accuracy Required = kD =  "<<accuracy<<"D";

       gotoxy(6,25);
       cout<<"Required Root :";

       gotoxy(6,26);
       cout<<"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍ";

       gotoxy(10,28);
       cout<<"x  =  "<<x;

       gotoxy(10,30);
       cout<<"Number of Iterations  =  "<<iterations;

       gotoxy(1,2);
    }