How to read user entered polynomial?

[sciman777]

So initially I thought this would be easy but apparently it's terribly hard. Downright impossible for me. I store the user input as a string and try to have the program analyse it character by character but this leads to major limitations, like the coefficients and powers can't be more than a single digit, I can't have more than a certain number of members, etc.

the point of the program is for the user to enter a polynomial, and have it automatically plug in numbers and spit out the answers.

thanks.

[lastchance]

Fundamentally, a polynomial over any field is just an array of numbers - the coefficients of the powers of its argument (which, incidentally, could be named anything).

Which would you rather have the user enter:
3 + 4x + 7x^3 - 2x^4
or
3 4 0 7 -2
(quite apart from the fact that x is essentially a placeholder, a dummy argument).

Enter your polynomial as a line of numbers, not a string.

[jonnin]

right, having the user enter zeros for missing terms makes it trivial. without that you have to do tons of work.

[tpb]

It's somewhat involved to read in a polynomial in a natural format, but it's not that bad. Use istringstream to make it easier.

I pecked away at this for half an hour or so and it's not quite there yet (and definitely not well-tested), but here's the idea. Storing the terms in a vector in whatever order they were read in (and not combining same-exponent terms) is obviously not the best storage scheme, but I was concentrating on parsing the input for now.

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stdexcept>

class Term {
public:
    static bool first_term;
    Term(std::istringstream& sin, bool neg=false);
    friend std::ostream& operator<<(std::ostream& os, const Term& p);
    static std::ostream& FirstTerm(std::ostream& os) {
        first_term = true;
        return os;
    }
private:
    double coef;
    int exponent;
};

bool Term::first_term = false;

std::ostream& operator<<(std::ostream& os, const Term& t) {
    double cf = t.coef;
    if (cf >= 0) {
        if (!Term::first_term)
            os << " + ";
    }
    else {
        os << " - ";
        cf = -cf;
    }
    if (cf != 1 || t.exponent == 0)
        os << cf;
    if (t.exponent != 0) {
        os << 'x';
        if (t.exponent != 1)
            os << '^' << t.exponent;
    }
    Term::first_term = false;
    return os;
}

Term::Term(std::istringstream& sin, bool neg) {
    sin >> coef;
    if (!sin) { sin.clear(); coef = 1.0; }
    if (neg) coef = -coef;
    char ch = '\0';
    sin >> ch;
    exponent = 0;
    if (ch == 'x') {
        exponent = 1;
        sin >> ch;
        if (ch == '^') {
            sin >> exponent;
            if (!sin)
                throw std::runtime_error("missing exponent");
        }
        else if (sin)
            sin.unget();
    }
}

class Poly {
public:
    Poly(std::string s);
    friend std::ostream& operator<<(std::ostream& os, const Poly& p);
private:
    std::vector<Term> terms;
};

std::ostream& operator<<(std::ostream& os, const Poly& p) {
    if (p.terms.size() == 0)
        os << '0';
    else {
        os << Term::FirstTerm << p.terms[0];
        for (size_t i = 1; i < p.terms.size(); i++)
            os << p.terms[i];
    }
    return os << " = 0";
}

Poly::Poly(std::string str) {
    std::istringstream sin(str);
    try {
        bool first = true;
        bool rhs = false;
        while (true) {
            // Look for +, -, or =
            char ch = '\0';
            sin >> ch;
            if (ch == '=') {
                if (first)
                    throw std::runtime_error("equals sign without lhs");
                if (rhs)
                    throw std::runtime_error("multiple equals signs");
                rhs = true;
                // Look for + or -
                sin >> ch;
                if (ch == '=')
                    throw std::runtime_error("multiple equals signs");
            }
            bool neg = false;
            if (ch == '-')
                neg = !neg;
            else if (ch != '+')
                sin.unget();
            if (sin) {
                Term term(sin, neg ^ rhs);
                terms.push_back(term);
                first = false;
            }
            else
                break;
        }
    }
    catch (std::exception& e) {
        std::cout << e.what() << '\n';
    }
}

int main() {
    std::string line;
    while (std::cout<<":: ", std::getline(std::cin, line)) {
        Poly p(line);
        std::cout << p << '\n';
    }
    std::cout << '\n';
}

[lastchance]

No error checking, but just about feasible. Could do with learning regex I think.

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <initializer_list>
#include <cctype>
using namespace std;


//=====================================================================


template <typename T> class polynomial                                                        // Polynomial over field of type T
{
   vector<T> coeff;
public:
   // Various constructors
   polynomial() { coeff = { T{} }; }                                                          // Construct as "zero"
   polynomial( const vector<T> &V ) { coeff = V; }                                            // Construct from a vector
   polynomial( const initializer_list<T> &V ) { coeff = vector<T>( V.begin(), V.end() ); }    // Construct from initialiser list
   polynomial( const string str, char X = 'x' );                                              // Construct from string

   T eval( T x );
};

//----------------------------

template <typename T> polynomial<T>::polynomial( const string str, char X )         // Construct from string
{
   // First strip blanks
   string s;
   for ( char c : str ) if ( !isspace( c ) ) s += c;

   // Break into units at every '+' or '-'; the limits will be [p,q)
   int p = 0, q = p;
   while ( q < s.size() )                                                     
   {
      for ( q = p + 1; q < s.size() && s[q] != '+' && s[q] != '-'; q++ );   
      string unit = s.substr( p, q - p );                                           // should be of form "cxn", meaning c times x^n

      // Pick out coefficient and exponent
      T c = 1;
      int n = 0;

      int pos = unit.find( X );                                                     // position of char X
      if ( pos == string::npos )                                                    // X not found; pure number
      {
         stringstream( unit ) >> c;
      }
      else                                                                          // identify coefficient (c) and exponent (n)
      {
         if ( pos != 0 )                                                            // pos == 0 would mean default c = 1
         {
            string first = unit.substr( 0, pos );
                 if ( first == "+" ) c = 1;                                         // just "+" means +1
            else if ( first == "-" ) c = -1;                                        // just "-" means -1
            else                     stringstream( first ) >> c;
         }

         if ( pos == unit.size() - 1 )
         {
            n = 1;
         }
         else
         {
            stringstream( unit.substr( pos + 1 ) ) >> n;
         }
      }

      if ( n + 1 > coeff.size() ) coeff.resize( n + 1 );
      coeff[n] += c;
      p = q;
   }
}

//----------------------------

template <typename T> T polynomial<T>::eval( T x )                                  // Evaluate polynomial at x
{
   T result = 0;
   for ( int r = coeff.size() - 1; r >= 0; r-- ) result = coeff[r] + result * x;
   return result;
}


//=====================================================================


int main()
{
   vector<double> V = { 1.0, 0.0, -3.0, 2.0 };
   polynomial<double> p( V );                              // vector
   polynomial<double> q( { 1.0, 0.0, -3.0, 2.0 } );        // initialiser list
   polynomial<double> r( " 1 - 3x2 + 2x3" );               // formula in 'x'
   polynomial<int>    s( "2t3 - 2t2 + 1 - t2", 't' );      // formula in 't', coefficients out of order and repeats

   cout << "x" << '\t' << "p(x)" << '\t' << "q(x)" << '\t' << "r(x)" << '\t' << "s(x)" << '\n';
   for ( int i = 0; i <= 10; i++ )
   {
       double arg = i;
       cout << arg << '\t'
            << p.eval( arg ) << '\t' 
            << q.eval( arg ) << '\t' 
            << r.eval( arg ) << '\t'
            << s.eval( i   ) << '\n';
   }   
}

x	p(x)	q(x)	r(x)	s(x)
0	1	1	1	1
1	0	0	0	0
2	5	5	5	5
3	28	28	28	28
4	81	81	81	81
5	176	176	176	176
6	325	325	325	325
7	540	540	540	540
8	833	833	833	833
9	1216	1216	1216	1216
10	1701	1701	1701	1701

[sciman777]

Thank you guys for your help! I think I need to learn more about C++ before I can do what I want to do. I don't know what vectors are nor templates.

What mid-level book would you recommend?