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.