An attempt to combine as terms for a template polynomial class using recursion in C ++

Question

I teach myself C ++.

I am trying to combine polynomials. To do this, I defined simple classes: Polynomial<T> , Term<T> and Coefficient<T> (which could also be just complex<T> ) using a simple composition of values. I defined the required operator overloads.

Polynomial comparison by sorting their members ( std::sort ).

I am working on combineLikeTerms() ; This method, when called first, will call another member method that will sort this vector of terms. For instance:

 4x^3 + 5x^2 + 3x - 4 

- possible resulting sorted vector.

Question

I use two iterators on this vector, and Im trying to merge neighboring members of the same order.

Let's say that our initial vector after sorting is as follows:

 4x^3 - 2x^3 + x^3 - 2x^2 + x ... 

after the function completes its iterations, then the stack vector temp looks like 2x ^ 3 + x ^ 3 - 2x ^ 2 + x ... if we look, that is, such terms still need to be reorganized again.

How can I do it? I am thinking about using recursion.

 // ------------------------------------------------------------------------- // // setPolynomialByDegreeOfExponent() // should be called before combineLikeTerms template <class T> void Polynomial<T>::setPolynomialByDegreeOfExponent() { unsigned int uiIndex = _uiNumTerms - 1; if ( uiIndex < 1 ) { return; } struct _CompareOperator_ { bool operator() ( math::Term<T> a, Term<T> b ) { return ( a.getDegreeOfTerm() > b.getDegreeOfTerm() ); } // operator() }; stable_sort( _vTerms.begin(), _vTerms.end(), _CompareOperator_() ); } // setPolynomialByDegreeOfExponent // ------------------------------------------------------------------------- // // addLikeTerms() template <class T> bool Polynomial<T>::addLikeTerms( const Term<T>& termA, const Term<T>& termB, Term<T>& result ) const { if ( termA.termsAreAlike( termB ) ) { result = termA + termB; return true; } return false; } // addLikeTerms // ------------------------------------------------------------------------- // // combineLikeTerms() template <class T> void Polynomial<T>::combineLikeTerms() { // First We Order Our Terms. setPolynomialByDegreeOfExponent(); // Nothing To Do Then if ( _vTerms.size() == 1 ) { return; } Term<T> result; // Temp Variable // No Need To Do The Work Below This If Statement This Is Simpler if ( _vTerms.size() == 2 ) { if ( addLikeTerms( _vTerms.at(0), _vTerms.at(1) ) { _vTerms.clear(); _vTerms.push_back( result ); } return; } // For 3 Ore More Terms std::vector<Term<T>> vTempTerms; // Temp storage std::vector<Term<T>>::iterator it = _vTerms.begin(); std::vector<Term<T>>::iterator it2 = _vTerms.begin()+1; bool bFound = addLikeTerms( *it, *it2, result ); while ( it2 != _vTerms.end() ) { if ( bFound ) { // Odd Case Last Three Elems if ( (it2 == (_vTerms.end()-2)) && (it2+1) == (_vTerms.end()-1)) ) { vTempTerms.push_back( result ); vTempTerms.push_back( _vTerms.back() ); break; } // Even Case Last Two Elems else if ( (it2 == (_vTerms.end()-1)) && (it == (_vTerms.end()-2)) ) { vTempTerms.push_back( result ); break; } else { vTempTerms.push_back( result ); it += 2; // Increment by 2 it2 += 2; " bFound = addLikeTerms( *it, *it2, result ); } } else { // Push Only First One vTempTerms.push_back( *it ); it++; // Increment By 1 it2++; " // Test Our Second Iterator if ( it2 == _vTerms.end() ) { vTempTerms.push_back( *(--it2) ); // same as using _vTerms.back() } else { bFound = addLikeTerms( *it, *it2, result ); } } } // Now That We Have Went Through Our Container, We Need To Update It _vTerms.clear(); _vTerms = vTempTerms; // At This point our stack variable should contain all elements from above, // however this temp variable can still have like terms in it. // ??? Were do I call the recursion and how do I define the base case // to stop the execution of the recursion where the base case is a // sorted std::vector of Term<T> objects that no two terms that are alike... // I do know that the recursion has to happen after the above while loop } // combineLikeTerms 

Can someone help me find the next step? I would be happy to hear about any errors / performance issues in the code shown. I love C ++

Answer 1

Here I take it upon myself in modern C ++.

Pay attention to additional optimization of dropping members with an effective coefficient of zero

Standalone sample: http://liveworkspace.org/code/ee68769826a80d4c7dc314e9b792052b

Update: Published C ++ 03 version of this http://ideone.com/aHuB8

 #include <algorithm> #include <vector> #include <functional> #include <iostream> template <typename T> struct Term { T coeff; int exponent; }; template <typename T> struct Poly { typedef Term<T> term_t; std::vector<term_t> _terms; Poly(std::vector<term_t> terms) : _terms(terms) { } void combineLikeTerms() { if (_terms.empty()) return; std::vector<term_t> result; std::sort(_terms.begin(), _terms.end(), [] (term_t const& a, term_t const& b) { return a.exponent > b.exponent; }); term_t accum = { T(), 0 }; for(auto 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 } }; int main() { Poly<int> demo({ { 4, 1 }, { 6, 7 }, {-3, 1 }, { 5, 5 } }); demo.combineLikeTerms(); for (auto it = demo._terms.begin(); it!= demo._terms.end(); ++it) std::cout << (it->coeff>0? " +" : " ") << it->coeff << "x^" << it->exponent; std::cout << "\n"; } 

Answer 2

You need to look at the polynomial as a sequence of pairs (coefficient, variable):

[(coefficient1, variable1), (coefficient2, variable2), (coefficient3, variable3), ...]

As you described, you iterate over it from left to right, combining two adjacent pairs into one when the variable part is identical (this, of course, assumes that the list has already been sorted by the variable part!).

Now, what happens when there are three or more elements in this list that share their variables? Well then just keep combining them. There is actually no need for recursion or anything complicated.

At any time during the iteration, you combine the variable part of the current pair with the variable part for the last time you saw it . If they are identical, you combine them and just continue. If in the next pair you will have the same variable part as the last, then you will combine them again. If you do it right, there should be no duplicates.

Here is an example of how to do this. It works by creating a new list of pairs, and then iterating through the input list, for each element of the input list, it decides whether to combine it with the element last clicked on the new list, or by adding a new element to the new list

 #include <utility> #include <vector> #include <iostream> typedef std::vector<std::pair<float,std::string>> Polynomial; Polynomial combine_like_terms(const Polynomial &poly) { if (poly.empty()) return poly; /* Here we store the new, cleaned-up polynomial: */ Polynomial clean_poly; /* Now we iterate: */ auto it = begin(poly); clean_poly.push_back(*it); ++it; while (it != end(poly)) { if (clean_poly.back().second == it->second) clean_poly.back().first += it->first; // Like term found! else clean_poly.push_back(*it); // Sequence of like-terms ended! ++it; } return clean_poly; } int main() { Polynomial polynomial { { 1.0 , "x^2" }, { 1.4 , "x^3" }, { 2.6 , "x^3" }, { 0.2 , "x^3" }, { 2.3 , "x" }, { 0.7 , "x" } }; Polynomial clean_polynomial = combine_like_terms(polynomial); for (auto term : clean_polynomial) std::cout << '(' << term.first << ',' << term.second << ")\n"; std::cout.flush(); return 0; } 

You can easily make this a template again if you need to - I used float for coefficients and strings for the variable part. This is really just a code example to show how this can be done easily without recursion or many iterators used in parallel.

Oh, and the code is written for C ++ 11. Again, this is just a model and can be adjusted for C ++ 03.