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:-
The syntax is the same in Micro$oft excel (spreadsheets)Code:5x² = 5x^2
When I enter:-
it correctly gives me:-Code:2(2x+5)-(x+4)-9(2x+5)
It also handles nested parentheses. Test if you can and report any bugs.Code:-15x-39
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.
EDIT*** changed the 'or' keywords it should compile on most compilers now.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);
}
}
