#include <iostream>
#include <cctype>
#include <cstdlib>
#include <vector>
#include <list>#include <algorithm>
using namespace std;
class Variable {
public:
char id;
int exp;
Variable() { // required by <vector>;
}
Variable(char c, int i) {
id = c; exp = i;
}
bool operator== (const Variable& v) const {
return id == v.id && exp == v.exp;
}
bool operator< (const Variable& v) const { // used by sort();
return id < v.id;
}
};
class Term {
public:
Term() {
coeff = 0;
}
int coeff;
vector<variable> vars;
bool operator== (const Term&) const;
bool operator!= (const Term& term) const { // required by <list>return !(*this == term);
}
bool operator< (const Term&) const;
bool operator> (const Term& term) const { // required by <list>return *this != term && (*this < term);
}
int min(int n, int m) const {
return (n < m) ? n : m;
}
};
class Polynomial {
public:
Polynomial() {
}
Polynomial operator+ (const Polynomial&) const;
void error(char *s) {
cerr << s << endl; exit(1);
}
private:
list<term> terms;
friend istream& operator>> (istream&, Polynomial&);
friend ostream& operator<< (ostream&, const Polynomial&);
};
bool Term::operator== (const Term& term) const {
int i;
for (int i = 0; i < min(vars.size(),term.vars.size()) &&vars[i] == term.vars[i]; i++);
return i == vars.size() && vars.size() == term.vars.size();
}
bool Term::operator< (const Term& term2) const { // used by sort();
if (vars.size() == 0)
return false; // *this is just a coefficient;
else if (term2.vars.size() == 0)
return true; // term2 is just a coefficient;
for (int i = 0; i < min(vars.size(),term2.vars.size()); i++)
if (vars[i].id < term2.vars[i].id)
return true; // *this precedes term2;
else if (term2.vars[i].id < vars[i].id)
return false; // term2 precedes *this;
else if (vars[i].exp < term2.vars[i].exp)
return true; // *this precedes term2;
else if (term2.vars[i].exp < vars[i].exp)
return false; // term2 precedes *this;
return ((int)vars.size()-(int)term2.vars.size() < 0) ? true : false;
}
Polynomial Polynomial::operator+ (const Polynomial& polyn2) const {
Polynomial result;
list<term>::iterator p1, p2;
bool erased;
for (p1 = terms.begin(); p1 != terms.end(); p1++) // create a new
result.terms.push_back(*p1); // polyn from
// copies of *this
for (p1 = polyn2.terms.begin; p1 != polyn2.terms.end(); p1++)
result.terms.push_back(*p1); // and polyn2;
for (p1 = result.terms.begin(); p1 != result.terms.end(); ) {
for (p2 = p1, p2++, erased = false; p2 != result.terms.end();
p2++)
if (*p1 == *p2) { // if two terms are equal (except
p1->coeff += p2->coeff; // for the coefficient), add the
result.terms.erase(p2); // two coefficients and erase
if (p1->coeff == 0) // a redundant term; if the
result.terms.erase(p1); // coefficient in retained
erased = true; // term is zero, break;
// erase the term as well;
}
if (erased) // restart processing from the beginning
p1 = result.terms.begin(); // if any node was erased;
else p1++;
}
result.terms.sort();
return result;
}
istream& operator>> (istream& in, Polynomial& polyn) {
char ch, sign, coeffUsed, id;
int exp;
Term term;
in >> ch;
while (true) {
coeffUsed = 0;
if (!isalnum(ch) && ch != ';' && ch != '-' && ch != '+')
polyn.error("Wrong character entered2");
sign = 1;
while (ch == '-' || ch == '+') { // first get sign(s) of Term
if (ch == '-')
sign *= -1;
ch = in.get();
if (isspace(ch))
in >> ch;
}
if (isdigit(ch)) { // and then its coefficient;
in.putback(ch);
in >> term.coeff;
ch = in.get();
term.coeff *= sign;
coeffUsed = 1;
}
else term.coeff = sign;
for (int i = 0; isalnum(ch); i++) { // process this term:
id = ch; // get a variable name
ch = in.get();
if (isdigit(ch)) { // and an exponent (if any);
in.putback(ch);
in >> exp >> ch;
}
else exp = 1;
term.vars.push_back(Variable(id,exp));
}
polyn.terms.push_back(term);// and include it in the linked list;
term.vars.resize(0);
if (isspace(ch))
in >> ch;
if (ch == ';') // finish if a semicolon is entered;
if (coeffUsed || i > 0)
break;
else polyn.error("Term is missing"); // e.g., 2x - ; or
// just ';'
else if (ch != '-' && ch != '+') // e.g., 2x 4y;
polyn.error("wrong character entered");
}
for (list<term>::iterator i = polyn.terms.begin();
i != polyn.terms.end(); i++)
if (i->vars.size() > 1)
sort(i->vars.begin(),i->vars.end());
return in;
}
ostream& operator<< (ostream& out, const Polynomial& polyn) {
int afterFirstTerm = 0, i;
for (list<term>::iterator pol = polyn.terms.begin();
pol != polyn.terms.end(); pol++) {
out.put(' ');
if (pol->coeff < 0) // put '-' before polynomial
out.put('-'); // and between terms (if
// needed);
else if (afterFirstTerm) // don’t put '+' in front of
out.put('+'); // polynomial;
afterFirstTerm++;
if (abs(pol->coeff) != 1) // print a coefficient
out << ' ' << abs(pol->coeff); // if it is not 1 nor -1, or
else if (pol->vars.size() == 0) // the term has only a
// coefficient
out << " 1";
else out.put(' ');
for (i = 1; i <= pol->vars.size(); i++) {
out << pol->vars[i-1].id; // print a variable name
if (pol->vars[i-1].exp != 1) // and an exponent, only
out << pol->vars[i-1].exp; // if it is not 1;
}
}
out << endl;
return out;
}
int main() {
Polynomial polyn1, polyn2;
cout << "Enter two polynomials, each ended with a semicolon:\n";
cin >> polyn1 >> polyn2;
cout << "The result is:\n" << polyn1 + polyn2;
return 0;
}