#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
template <typename T> struct Term
{
Term() : coeff(), exponent(0) { }
Term(T c, int e) : coeff(c), exponent(e) { }
T coeff;
int exponent;
};
template <typename T> struct Poly
{
typedef Term<T> term_t;
typedef std::vector<term_t> terms_t;
terms_t _terms;
Poly(terms_t terms) : _terms(terms) { }
void combineLikeTerms()
{
if (_terms.empty())
return;
std::sort(_terms.begin(), _terms.end(), order);
term_t accum(T(), 0);
std::vector<term_t> result;
for (typename terms_t::const_iterator curr = _terms.begin(); curr!= _terms.end(); ++curr)
{
if (curr->exponent == accum.exponent)
accum.coeff += curr->coeff;
else
{
if (accum.coeff != 0)
result.push_back(accum);
accum = *curr;
}
}
if (accum.coeff != 0)
result.push_back(accum);
std::swap(_terms, result); // only update if no exception
}
private:
static bool order(term_t const& a, term_t const& b)
{ return a.exponent > b.exponent; }
};
int main()
{
Poly<int>::terms_t terms;
terms.push_back(Term<int>( 4, 1 ));
terms.push_back(Term<int>( 6, 7 ));
terms.push_back(Term<int>(-3, 1 ));
terms.push_back(Term<int>( 5, 5 ));
Poly<int> demo(terms);
typedef std::vector<Term<int> >::const_iterator It;
demo.combineLikeTerms();
for (It it = demo._terms.begin(); it!= demo._terms.end(); ++it)
std::cout << (it->coeff>0? " +" : " ") << it->coeff << "x^" << it->exponent;
std::cout << "\n";
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCnRlbXBsYXRlIDx0eXBlbmFtZSBUPiBzdHJ1Y3QgVGVybQp7CiAgICBUZXJtKCkgOiBjb2VmZigpLCBleHBvbmVudCgwKSB7IH0KICAgIFRlcm0oVCBjLCBpbnQgZSkgOiBjb2VmZihjKSwgZXhwb25lbnQoZSkgeyB9CiAgICBUIGNvZWZmOwogICAgaW50IGV4cG9uZW50Owp9OwoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+IHN0cnVjdCBQb2x5CnsKICAgIHR5cGVkZWYgVGVybTxUPiB0ZXJtX3Q7CiAgICB0eXBlZGVmIHN0ZDo6dmVjdG9yPHRlcm1fdD4gdGVybXNfdDsKICAgIHRlcm1zX3QgX3Rlcm1zOwoKICAgIFBvbHkodGVybXNfdCB0ZXJtcykgOiBfdGVybXModGVybXMpIHsgfQoKICAgIHZvaWQgY29tYmluZUxpa2VUZXJtcygpCiAgICB7CiAgICAgICAgaWYgKF90ZXJtcy5lbXB0eSgpKQogICAgICAgICAgICByZXR1cm47CgogICAgICAgIHN0ZDo6c29ydChfdGVybXMuYmVnaW4oKSwgX3Rlcm1zLmVuZCgpLCBvcmRlcik7CgogICAgICAgIHRlcm1fdCBhY2N1bShUKCksIDApOwogICAgICAgIHN0ZDo6dmVjdG9yPHRlcm1fdD4gcmVzdWx0OwoKICAgICAgICBmb3IgKHR5cGVuYW1lIHRlcm1zX3Q6OmNvbnN0X2l0ZXJhdG9yIGN1cnIgPSBfdGVybXMuYmVnaW4oKTsgY3VyciE9IF90ZXJtcy5lbmQoKTsgKytjdXJyKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGN1cnItPmV4cG9uZW50ID09IGFjY3VtLmV4cG9uZW50KQogICAgICAgICAgICAgICAgYWNjdW0uY29lZmYgKz0gY3Vyci0+Y29lZmY7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKGFjY3VtLmNvZWZmICE9IDApCiAgICAgICAgICAgICAgICAgICAgcmVzdWx0LnB1c2hfYmFjayhhY2N1bSk7CiAgICAgICAgICAgICAgICBhY2N1bSA9ICpjdXJyOwogICAgICAgICAgICB9CiAgICAgICAgfSAgICAgICAgCiAgICAgICAgaWYgKGFjY3VtLmNvZWZmICE9IDApCiAgICAgICAgICAgIHJlc3VsdC5wdXNoX2JhY2soYWNjdW0pOwoKICAgICAgICBzdGQ6OnN3YXAoX3Rlcm1zLCByZXN1bHQpOyAvLyBvbmx5IHVwZGF0ZSBpZiBubyBleGNlcHRpb24KICAgIH0KCiAgcHJpdmF0ZTogCiAgICBzdGF0aWMgYm9vbCBvcmRlcih0ZXJtX3QgY29uc3QmIGEsIHRlcm1fdCBjb25zdCYgYikKICAgICAgICB7IHJldHVybiBhLmV4cG9uZW50ID4gYi5leHBvbmVudDsgfQp9OwoKaW50IG1haW4oKQp7CiAgICBQb2x5PGludD46OnRlcm1zX3QgdGVybXM7CiAgICB0ZXJtcy5wdXNoX2JhY2soVGVybTxpbnQ+KCA0LCAxICkpOwogICAgdGVybXMucHVzaF9iYWNrKFRlcm08aW50PiggNiwgNyApKTsKICAgIHRlcm1zLnB1c2hfYmFjayhUZXJtPGludD4oLTMsIDEgKSk7CiAgICB0ZXJtcy5wdXNoX2JhY2soVGVybTxpbnQ+KCA1LCA1ICkpOwoKICAgIFBvbHk8aW50PiBkZW1vKHRlcm1zKTsKCiAgICB0eXBlZGVmIHN0ZDo6dmVjdG9yPFRlcm08aW50PiA+Ojpjb25zdF9pdGVyYXRvciBJdDsKICAgICAgICAKICAgIGRlbW8uY29tYmluZUxpa2VUZXJtcygpOwoKICAgIGZvciAoSXQgaXQgPSBkZW1vLl90ZXJtcy5iZWdpbigpOyBpdCE9IGRlbW8uX3Rlcm1zLmVuZCgpOyArK2l0KQogICAgICAgIHN0ZDo6Y291dCA8PCAoaXQtPmNvZWZmPjA/ICIgKyIgOiAiICIpIDw8IGl0LT5jb2VmZiA8PCAieF4iIDw8IGl0LT5leHBvbmVudDsKCiAgICBzdGQ6OmNvdXQgPDwgIlxuIjsKfQ==