# Algebraic Fractions

Printable View

• 12-19-2005
treenef
Algebraic Fractions
Algebraic Fractions

Ok so I have most of my Algebra program working at the moment.
A lot of the code is quite ugly but I intend to clean that up later.

My program so far handles the addition,subtraction and multiplication of univarate equations. Not DIVISION yet.

The syntax is intuitive. To enter an exponent you use the '^' eg:-

Code:

`5x² = 5x^2`
The syntax is the same in Micro\$oft excel (spreadsheets)

When I enter:-

Code:

`2(2x+5)-(x+4)-9(2x+5)`
it correctly gives me:-

Code:

`-15x-39`
It also handles nested parentheses. Test if you can and report any bugs.

It doesn't solve equations as yet so don't bother using the equals sign. I intend to use the Newton-Raphson method for this later.

Anyway, my question is how should I go about designing a system to solve equations with fractions...

Code:

```2  -  x + 4  =  9     ------     2x + 5```

Thanks for your time.

Code:

```/*  Filename: Algebra IV     To actually implement polynomial addition,subtraction     and multiplication using postfix notation         V.0.4         */ #include <iostream> #include <string> #include <stack> #include <vector> #include <sstream> using namespace std; void Convert(const string & Infix, string & Postfix); bool IsOperand(char ch); bool TakesPrecedence(char OperatorA, char OperatorB); /*===================================================  My functions declared below:-  ===================================================*/ string Tokenise_Expression(string); string Insert_comma(string); //ammended below void Next(string); /*====================================================   My polynomial functions declared below:-   ===================================================*/ string Num_to_Poly(string); string Poly_to_Num(string); //cout<<Catch_Case(Poly_to_Num("13x^13")); string Tokenise(string); bool Is_Operand(char); //different from other function int Get_Coeff(string); int Get_Expo(string); string Catch_Case(string); string Sub_Poly(string,string); string Mult_Poly(string,string); string Add_Poly(string,string); int String_to_Int(string); string Int_to_String(int); string Eval(string[]); int main(void) {   char Reply;   do       {       string Infix, Postfix;  // local to this loop       cout <<"Enter your expression with no spaces:\n>> ";       cin >> Infix;                   string temp,hemp,lemp;       temp = Tokenise_Expression(Infix);       //lemp=Rogue_Case(temp);       Convert(temp, Postfix);       hemp = Insert_comma(Postfix);             //cout << "The equivalent postfix expression is:" << endl         //<< hemp << endl;                 //call function Next         Next(hemp);               cout << endl << "Do another (y/n)? ";       cin >> Reply;       }   while (tolower(Reply) == 'y');   return 0; } /* =======================================================================   Given:  ch  A character.   Task:  To determine whether ch represents an operand (here understood           to be a single letter or digit).   Return: In the function name: true, if ch is an operand, false otherwise.   ======================================================================*/ bool IsOperand(char ch) {   if (((ch >= 'a') && (ch <= 'z')) ||       ((ch >= 'A') && (ch <= 'Z')) ||       ((ch >= '0') && (ch <= '9')) ||       ((ch == '^') || (ch == '\$')))             return true;   else       return false; } /* =========================================================================   Given:  OperatorA    A character representing an operator or parenthesis.           OperatorB    A character representing an operator or parenthesis.   Task:  To determine whether OperatorA takes precedence over OperatorB.   Return: In the function name: true, if OperatorA takes precedence over           OperatorB.   =======================================================================*/ bool TakesPrecedence(char OperatorA, char OperatorB) {   if (OperatorA == '(')       return false;   else if (OperatorB == '(')       return false;   else if (OperatorB == ')')       return true;   else if ((OperatorA == '*'))       return true;   else if ((OperatorB == '*'))       return false;   else       return true;       /* omit division for the time being since it requires a more       * rigid definition       */       } /* =======================================================================   Given:  Infix    A string representing an infix expression (no spaces).   Task:  To find the postfix equivalent of this expression.   Return: Postfix  A string holding this postfix equivalent.   =======================================================================*/ void Convert(const string & Infix, string & Postfix) {   stack<char> OperatorStack;   char TopSymbol, Symbol;   int k;   for (k = 0; k < Infix.size(); k++)   {                   Symbol = Infix[k];         if (Symbol == ',')         {           Postfix = Postfix + ",";           //insert a comma where found         }                      else if (IsOperand(Symbol))         Postfix = Postfix + Symbol;       else         {         while ((! OperatorStack.empty()) &&             (TakesPrecedence(OperatorStack.top(), Symbol)))             {             TopSymbol = OperatorStack.top();             OperatorStack.pop();             Postfix = Postfix + TopSymbol;             }         if ((! OperatorStack.empty()) && (Symbol == ')'))             OperatorStack.pop();  // discard matching (         else             OperatorStack.push(Symbol);         }     }   while (! OperatorStack.empty())   {       TopSymbol = OperatorStack.top();       OperatorStack.pop();       Postfix = Postfix + TopSymbol;   }    } /*=========================================  Function description:   To tokenise expression   by inserting commas at the relevant places.   Returns a string  ==========================================*/   string Tokenise_Expression(string my_string) {       //--------------------------     for(int i=0; i<my_string.length(); i++)     {         if(my_string[i]=='(')         {           if(my_string[i-1]=='-')           {               my_string.replace(i,1,"1(");           }                          }     }     //cout<< my_string;     //cin.get();     //------------------------     for(int i = 0; i <my_string.length(); i++)     {         if((my_string[i]=='(')&&(i!=0))         {             if((my_string[i-1]!='(')&&               (my_string[i-1]!='*')&&               (my_string[i-1]!='+'))               {                   my_string.replace(i,1,"*(");                   //  (2 + x)(3 - x)                   // =>(2 + x)*(3 - x)               }           }     }               for(int i = 0; i <my_string.length(); i++)     {       if(isdigit(my_string[i])!=0)       {           if((isdigit(my_string[i+1])==0)&&             (IsOperand(my_string[i+1])== false))             {                my_string.insert(i+1, ",");                           }          }        }         for(int i = 0; i <my_string.length(); i++)     {       if((my_string[i]=='x')&&(my_string[i+1]!='^'))       {           if(isdigit(my_string[i+1])==0)           {                my_string.insert(i+1, ",");                           }          }        }     //Changed -7*-7 case     for (int i = 0; i <my_string.length(); i++)     {         if(my_string[i]=='-')         {             if((my_string[i-1]!=',')&&(my_string[i-1]!=')'))             {               my_string.replace(i,1,"\$");             }         }     }     //cout<<"\n\n";     //cout<<my_string<<endl;     //cin.get();     return my_string; }    /*========================================   My function needed to tokenise expression   ========================================*/ string Insert_comma(string my_string) {         for(int i = 0; i <my_string.length(); i++)     {       if((my_string[i]=='*')||         (my_string[i]=='-')||         (my_string[i]=='/')||         (my_string[i]=='+'))           {             my_string.insert(i+1, ",");             //Insert a comma after all             //found operators           }                         }         for (int i = 0; i <my_string.length(); i++)     {         if(my_string[i]=='\$')         {             my_string.replace(i,1,"-");             //replace the '\$' with a '-'         }     }        return my_string; } //ammended----------------------------------------------- /*===============================   Function to convert all numbers   into polys   ===============================*/ string Num_to_Poly(string my_string) {     int count=0;     for(int i=0; i<my_string.length(); i++)     {         if(my_string[i]=='x')         {             count++;             if(isdigit(my_string[i-1])==0)             {               my_string.replace(i,1,"1x");             }            }               }     if(count==0)     {       my_string.replace(my_string.length(),1,"x^0");     }      for(int i=0; i<my_string.length(); i++)     {         if(my_string[i]=='x')         {             if(my_string[i+1]!='^')             {               my_string.insert(i+1,"^1");             }                        }     }     return my_string; } /*==========================================  Function to tokenise expression with  commas  ==========================================*/ string Tokenise(string my_string) { for(int i = 0; i <my_string.length(); i++)     {       if(isdigit(my_string[i])!=0)       {           if((isdigit(my_string[i+1])==0)&&             (Is_Operand(my_string[i+1])== false))             {                my_string.insert(i+1, ",");                           }          }        }         for(int i = 0; i <my_string.length(); i++)     {       if((my_string[i]=='x')&&(my_string[i+1]!='^'))       {           if(isdigit(my_string[i+1])==0)           {                my_string.insert(i+1, ",");                           }          }        }      return my_string; } /*============================================  Function to check if it is an operand  =============================================*/      bool Is_Operand(char ch) {   if (((ch >= 'a') && (ch <= 'z')) ||       ((ch >= 'A') && (ch <= 'Z')) ||       ((ch >= '0') && (ch <= '9')) ||       ((ch == '^') || (ch == '\$')))             return true;   else       return false; } /*===============================================   Function to convert Polys back to nums   ==============================================*/ string Poly_to_Num(string my_string) {             if(  ((Get_Coeff(my_string)==1)||         (Get_Coeff(my_string)==-1))&&         (Get_Expo(my_string)!=0)       )       {             int tag=0;             for(int i=0; i<my_string.length(); i++)             {               if(my_string[i]=='x')               {                 tag=i-1;               }             }                  my_string.erase(tag, 1); // erases 1                     return my_string;         }                 if(Get_Expo(my_string)==1)       {         int tag=0;         for(int i=0; i<my_string.length(); i++)         {             if(my_string[i]=='^')             {                 tag=i;             }         }         my_string.erase(tag, 2); // erases ^1         return my_string;                   }     if(Get_Expo(my_string)==0)     {         int tag=0;         for(int i=0; i<my_string.length(); i++)         {             if(my_string[i]=='x')             {                 tag=i;             }         }                 my_string.erase(tag, 3); // erases x^0       return my_string;             }      return my_string;  //else do nothing  }    /*=============================================   Function to get coefficient   Returns an integer   ============================================*/ int Get_Coeff(string my_string) {     //before the x     string coeff="";     for(int i=0; i<my_string.length(); i++)     {         if(my_string[i]!='x')         {             coeff=coeff + my_string[i];         }         else if(my_string[i]=='x')         {             break;         }        }         int k;     //convert to integer     istringstream ins;     ins.str(coeff);     ins >> k;         return k;               cin.get(); } /*==========================================   Function to get exponent   Returns an integer   ==========================================*/ int Get_Expo(string my_string) {       //after the x     int pass=0;     string coeff="";     for(int i=0; i<my_string.length(); i++)     {               if (pass==1)         {             coeff=coeff + my_string[i];         }           if(my_string[i]=='^')         {             pass=1;         }              }         int k;     //convert to integer     istringstream ins;     ins.str(coeff);     ins >> k;         return k;               cin.get();  }    /*=================================   function catch case   =================================*/ string Catch_Case(string changer) {     if((changer=="x^1")||(changer=="+x^1"))     {         changer="+x";     }     if(changer=="-x^1")     {         changer="-x";     }        return changer; }  /*=================================   function int to string   =================================*/ string Int_to_String(int k) {     string ch;   ostringstream outs;  // Declare an output string stream.   outs << k;  // Convert value into a string.   return outs.str(); } /*=================================   function string to int   =================================*/ int String_to_Int(string my_string) {         int x;     istringstream ins;     ins.str(my_string);     ins >> x;     return x; }    /*==============================================   My function to actually subtract two   strings   =============================================*/ string Sub_Poly(string A,string B) {     string A_bling,B_bling;     A_bling = Tokenise(A);     B_bling = Tokenise(B);           vector <string> array; //create a vector of strings     vector <string> array_b;     string tempy;     string tempie;       int comma_count_A=0;     for (int a=0; a<A_bling.length();a++)     {       if(A_bling[a]==',')       {           comma_count_A++;       }     }     int comma_count_B=0;     for (int a=0; a<B_bling.length();a++)     {       if(B_bling[a]==',')       {           comma_count_B++;       }     }                //---------------------------------------------     //Evaluate tokens using the "," as a delimiter     while (A_bling.find(",", 0) != string::npos)     {     //lifted from the FAQ     //does the string have a comma in it?     size_t pos = A_bling.find(",", 0);     tempy = A_bling.substr(0, pos);          A_bling.erase(0, pos + 1);              array.push_back(tempy); //store in vector                  }     array.push_back(A_bling);//the last token is all alone         for(int j=0; j<array.size()-1; j++)     {         string ben = Num_to_Poly(array[j]);         array[j]= ben;     }     //---------------------------------     // cout<<"\n";     while (B_bling.find(",", 0) != string::npos)     {     //lifted from the FAQ     //does the string have a comma in it?     size_t pos = B_bling.find(",", 0);     tempie = B_bling.substr(0, pos);          B_bling.erase(0, pos + 1);              array_b.push_back(tempie); //store in vector                  }     array_b.push_back(B_bling);//the last token is all alone         for(int j=0; j<array_b.size()-1; j++)     {         string hen = Num_to_Poly(array_b[j]);         array_b[j] = hen;     }         //---------------------------------------     int rcoef[100];     //initialise them     for(int i=0; i<100; i++)     {         rcoef[i]=0;     }     for(int i=0; i<comma_count_A; i++)     {         rcoef[Get_Expo(array[i])]=rcoef[Get_Expo(array[i])]+         Get_Coeff(array[i]);     }     for(int i=0; i<comma_count_B; i++)     {         rcoef[Get_Expo(array_b[i])]=rcoef[Get_Expo(array_b[i])]-         Get_Coeff(array_b[i]);     }       string final="";               for(int i=99; i>=0; i--)         {              if(rcoef[i]!=0)             {                 string jemp;                 string insert;                               if(rcoef[i]>0)                 {                                         insert="+";                 }                 else                 {                     insert="";                 }                        jemp=                 insert+Int_to_String(rcoef[i])+"x^"+Int_to_String(i);                 final=final+Catch_Case(Poly_to_Num(jemp));             }            }         return final;        } /*==============================================   My function to actually multipy two   strings   =============================================*/ string Mult_Poly(string A,string B) {     string A_bling,B_bling;     A_bling = Tokenise(A);     B_bling = Tokenise(B);           vector <string> array; //create a vector of strings     vector <string> array_b;     string tempy;     string tempie;       int comma_count_A=0;     for (int a=0; a<A_bling.length();a++)     {       if(A_bling[a]==',')       {           comma_count_A++;       }     }     int comma_count_B=0;     for (int a=0; a<B_bling.length();a++)     {       if(B_bling[a]==',')       {           comma_count_B++;       }     }                //---------------------------------------------     //Evaluate tokens using the "," as a delimiter     while (A_bling.find(",", 0) != string::npos)     {     //lifted from the FAQ     //does the string have a comma in it?     size_t pos = A_bling.find(",", 0);     tempy = A_bling.substr(0, pos);          A_bling.erase(0, pos + 1);              array.push_back(tempy); //store in vector                  }     array.push_back(A_bling);//the last token is all alone         for(int j=0; j<array.size()-1; j++)     {         string ben = Num_to_Poly(array[j]);         array[j]= ben;     }     //---------------------------------     //cout<<"\n";     while (B_bling.find(",", 0) != string::npos)     {     //lifted from the FAQ     //does the string have a comma in it?     size_t pos = B_bling.find(",", 0);     tempie = B_bling.substr(0, pos);          B_bling.erase(0, pos + 1);              array_b.push_back(tempie); //store in vector                  }     array_b.push_back(B_bling);//the last token is all alone         for(int j=0; j<array_b.size()-1; j++)     {         string hen = Num_to_Poly(array_b[j]);         array_b[j] = hen;     }         //---------------------------------------     int rcoef[100];     //initialise them     for(int i=0; i<100; i++)     {         rcoef[i]=0;     }         for(int i=0; i<comma_count_A; i++)     {         for(int j=0; j<comma_count_B; j++)         {             rcoef[Get_Expo(array[i])+ Get_Expo(array_b[j])]=             rcoef[Get_Expo(array[i])+ Get_Expo(array_b[j])] +             Get_Coeff(array[i])* Get_Coeff(array_b[j]);         }     }                    string final="";                 for(int i=99; i>=0; i--)         {              if(rcoef[i]!=0)             {                 string jemp;                 string insert;                 //jemp=Int_to_String(rcoef[i])+"x^"+Int_to_String(i)+" ";                 //cout<<Catch_Case(Poly_to_Num(jemp));                 if(rcoef[i]>0)                 {                                         insert="+";                 }                 else                 {                     insert="";                 }                        jemp=                 insert+Int_to_String(rcoef[i])+"x^"+Int_to_String(i);                 final=final+Catch_Case(Poly_to_Num(jemp));                             }            }          return final;      }  /*==============================================   My function to actually add two   strings   =============================================*/ string Add_Poly(string A,string B) {     string A_bling,B_bling;     A_bling = Tokenise(A);     B_bling = Tokenise(B);           vector <string> array; //create a vector of strings     vector <string> array_b;     string tempy;     string tempie;       int comma_count_A=0;     for (int a=0; a<A_bling.length();a++)     {       if(A_bling[a]==',')       {           comma_count_A++;       }     }     int comma_count_B=0;     for (int a=0; a<B_bling.length();a++)     {       if(B_bling[a]==',')       {           comma_count_B++;       }     }                //---------------------------------------------     //Evaluate tokens using the "," as a delimiter     while (A_bling.find(",", 0) != string::npos)     {     //lifted from the FAQ     //does the string have a comma in it?     size_t pos = A_bling.find(",", 0);     tempy = A_bling.substr(0, pos);          A_bling.erase(0, pos + 1);              array.push_back(tempy); //store in vector                  }     array.push_back(A_bling);//the last token is all alone         for(int j=0; j<array.size()-1; j++)     {         string ben = Num_to_Poly(array[j]);         array[j]= ben;     }     //---------------------------------     cout<<"\n";     while (B_bling.find(",", 0) != string::npos)     {     //lifted from the FAQ     //does the string have a comma in it?     size_t pos = B_bling.find(",", 0);     tempie = B_bling.substr(0, pos);          B_bling.erase(0, pos + 1);              array_b.push_back(tempie); //store in vector                  }     array_b.push_back(B_bling);//the last token is all alone         for(int j=0; j<array_b.size()-1; j++)     {         string hen = Num_to_Poly(array_b[j]);         array_b[j] = hen;     }         //---------------------------------------     int rcoef[100];     //initialise them     for(int i=0; i<100; i++)     {         rcoef[i]=0;     }     for(int i=0; i<comma_count_A; i++)     {         rcoef[Get_Expo(array[i])]=rcoef[Get_Expo(array[i])]+         Get_Coeff(array[i]);     }     for(int i=0; i<comma_count_B; i++)     {         rcoef[Get_Expo(array_b[i])]=rcoef[Get_Expo(array_b[i])]+         Get_Coeff(array_b[i]);     }       string final="";         for(int i=99; i>=0; i--)         {              if(rcoef[i]!=0)             {                 string jemp;                 string insert;                               if(rcoef[i]>0)                 {                                         insert="+";                 }                 else                 {                     insert="";                 }                        jemp=                 insert+Int_to_String(rcoef[i])+"x^"+Int_to_String(i);                 final=final+Catch_Case(Poly_to_Num(jemp));             }            }         return final;        }  /*==================================================================   function to evaluate expression   ================================================================*/ void Next(string my_string) {   vector <string> array;   string tempy;     int comma_count=0;   for (int a=0; a<my_string.length();a++)   {       if(my_string[a]==',')       {           comma_count++;       }   }          //Evaluate tokens using the "," as a delimiter   while (my_string.find(",", 0) != string::npos)   {     //lifted from the FAQ     //does the string have a comma in it?     size_t pos = my_string.find(",", 0);     tempy = my_string.substr(0, pos);          my_string.erase(0, pos + 1);              array.push_back(tempy); //store in vector                }   //array.push_back(my_string);//the last token is all alone     stack <string> my_stack;//initialise stack   string temp[100];   string ch;     for (int i=0; i<comma_count; i++)   {             string s;       s=array[i]; //make it easier to read             if ((s!="+")&&           (s!="*")&&           (s!="-")&&           (s!="/"))           {             my_stack.push(s);             //push numbers onto the stack           }         else //i.e if it encounters an operator         {               my_stack.push(s);//push operator onto stack               temp[0]= my_stack.top();//store value               my_stack.pop(); //erase from the stack                           temp[1]= my_stack.top();//store value               my_stack.pop();//erase from the stack                             temp[2]= my_stack.top();//store value               my_stack.pop();//erase from the stack                                         ch = Eval(temp);                           my_stack.push(ch);             }                  }   if(ch[0]=='+')   {       ch.erase(0,1);//erase first plus sign   }   cout<<ch;        cin.get(); }    /*=================================================*/ string Eval(string temp[]) {     string a,b,c;     a=temp[2]; b=temp[0]; c=temp[1];             if (b=="+")     {       return Add_Poly(a,c);             }     else if (b=="-")     {         return Sub_Poly(a,c);     }     else if (b=="*")     {         return Mult_Poly(a,c);     }                 }```
EDIT*** changed the 'or' keywords it should compile on most compilers now.
• 12-19-2005
elad
In my version I did something like this:
Code:

```2  -  x + 4  =  9     ------     2x + 5```
is really this:

a + b = c

where:

a = a/1;
b = -1(x + 4)/(2x + 5);
c = 9/1;

This demonstrates explicitly that each operand a. b and c is really a fraction and each fraction has a polynomial numerator and a polynomial denominator. The goal is to get all denominators to 1. Then you can solve the equation as though it wasn't a rational expression. Restricting expression to using integer coefficients proved doable, particularly if I restrited the definition of 1 to be just 1 and not 0x^2 + 0x^1 + 2^0 or whatever else equates to 1 when everything is said and done.

Trickier was allowing all coefficients to be rational:

[code]
2/3 - 2(x + 4/5)/3(2x/7 - 5/8) = 9/17;

and then allowing nested parenthesis with rational coefficients was too much. I didn't complete that one satisfactorily.

In my system I used a schema something like this:

An equation is two expressions separated by an = operator
An expression is a single operand or multiple operands separated by a + operator
An operand has a numerator and denominator.
Each numerator and denominator can be a parenthetical expression.
Each parenthetical expression can have no, one parenthetical pair, or nested parenthetical pairs.
Within each parenthetical pair is a polynomial expression.
A polynomial expression is a sequence of one or more terms separated by a + operator.
Each term can have a coefficient, a base and an exponent.
Each coefficient may be an integer or a fraction.
Each base is a single char.
Each exponent is an integer.

Good luck on your continued explorations into the joys of writing your own mathematical library.
• 12-19-2005
Darryl
FYI: you can post attachments to your message.

Would not compile because you are using "or" keywords instead of ||.

Now there is an or keyword but you have to include a certain header that I don't know off the top of my head.

EDIT:
I looked up the header, it's #include <iso646.h>, but it's not capital, it's lowercase like you have it.
• 12-19-2005
Darryl
I am getting a lot of assertion errors for instance;

3(10) returns 30; correct
(3)10 gives me debug assertion fails
• 12-19-2005
treenef
Yeah, sorry bout the or keywords, I was just experimenting and was meant to take that out... replace itwith the standard ||, never got round to it.

Dev c++ seems to handle it without any other specific header files.

Quote:

(3)10 gives me debug assertion fails
I deliberately,left those cases where multiplication happens after the bracket:-

Code:

`(10)-4`
For example, does that evaluate to 6 or -40.

Other assertion errors are because I haven't written a code to catch errors. It's fairly simple anyway, I'll do that later. I just need to get this working.

Cheers elad I'll look into that.
• 12-19-2005
treenef
Ok Darryl, I'm changing the code to handle the cases you have mentioned.

Other than that though, are there any other errors. By that,
I mean cases that are legal but my program gets wrong.

Code:

`2/3 - 2(x + 4/5)/3(2x/7 - 5/8) = 9/17;`
elad nested division is evil.

:p
• 12-19-2005
Enahs
In my version I went and bought Maple 10 because I use it everyday, for things way more advanced than basic algebra calculations, though it does those beautifully :)
http://www.maplesoft.com/
• 12-19-2005
Darryl
I don't kow if this is right or wrong, maybe you can enlighten me
>> (x2)*3
3x^12

I have another suggestion, instead of asking do you want to continue, just continue like until "quit" is entered or something
• 12-20-2005
treenef
Code:

```>> (x2)*3 3x^12```
That would be regarded as an invalid entry. As yet I haven't writen code for that...

it would either be:-

Code:

```(2x)*3 = 6x or (x^2)*3 = 3x^2```
Other than that though, have you noticed any other bugs or problems. Could you test multiple nesting in particular?

Quote:

In my version I went and bought Maple 10 because I use it everyday, for things way more advanced than basic algebra calculations, though it does those beautifully
Now where's the fun in that???

;)