C++ extract polynomial coefficients

Question

So I have a polynomial that looks like this: -4x^0 + x^1 + 4x^3 - 3x^4
I can tokenize this by space and '+' into: -4x^0, x^1, 4x^3, -, 3x^4

How could I just get the coefficients with the negative sign: -4, 1, 0, 4, -3
x is the only variable that will appear and this will alway appear in order
im planning on storing the coefficients in an array with the array index being the exponent
so: -4 would be at index 0, 1 would be at index 1, 0 at index 2, 4 at index 3, -3 at index 4

Answer 1

Start with "-4x^0 + x^1 + 4x^3 - 3x^4"
Split after ^number: "-4x^0", " + x^1", " + 4x^3", " - 3x^4"
Now everything behind an ^ is an exponent, everything before the x is an coefficient

EDIT: Simple method to get the coefficient (including the sign):

Init coefficient with 0, sign with '+'
Go through each character before the x from left to right
  If it's a number ('0'..'9'), coefficient = coefficient * 10 + number
  If it's '-', set sign to '-'

Answer 2

For a quick solution, my approach would be to write a recursive descent parser. Move forward in the string and extract the components you want. There are many examples around for writing a parser of an expression like this.

If you want to use a library, you could use boost::regex or boost::spirit, depending on what kind of approach you want to take.

Answer 3

Once you have tokenized to "-4x^0", "x^1", etc. you can use strtol() to convert the textual representation into a number. strtol will automatically stop at the first non-digit character so the 'x' will stop it; strtol will give you a pointer to the character that stoped it, so if you want to be paranoid, you can verify the character is an x.

You will need to treat implicit 1's (i.e. in "x^1" specially). I would do something like this:

long coeff;
if (*token == 'x')
{
   coeff = 1;
}
else
{
    char *endptr;
    coeff = strtol(token, &endptr, 10);
    if (*endptr != 'x')
    {
        // bad token
    }  
}

Answer 4

scan the string for an 'x', then go backward storing each character of the coefficient until you hit white space. eg:

for (int i=0; i<s.length(); ++i)
{
    if (s[i] == 'x')
    {
     string c;
     for (int j=i-1; j>=0 && s[j]!=' '; --j)
      c = s[j] + c;
     cout << "coefficient: " << c << endl;
    }
}

Answer 5

Write a simple tokenizer. Define a number token (/[-0123456789][0123456789]+/), an exponent token (/x^(::number::)/). Ignore whitespace and +.

Continually read tokens as you'd expect them until the end of the string. Then spit out the tokens in whatever form you want (e.g. integers).

int readNumber(const char **input) {
    /* Let stdio read it for us. */
    int number;
    int charsRead;
    int itemsRead;

    itemsRead = sscanf(**input, "%d%n", &number, &charsRead);

    if(itemsRead <= 0) {
        // Parse error.
        return -1;
    }

    *input += charsRead;

    return number;
}

int readExponent(const char **input) {
    if(strncmp("x^", *input, 2) != 0) {
        // Parse error.
        return -1;
    }

    *input += 2;

    return readNumber(input);
}

/* aka skipWhitespaceAndPlus */
void readToNextToken(const char **input) {
    while(**input && (isspace(**input) || **input == '+')) {
        ++*input;
    }
}

void readTerm(const char **input. int &coefficient, int &exponent, bool &success) {
    success = false;

    readToNextToken(input);

    if(!**input) {
        return;
    }

    coefficient = readNumber(input);

    readToNextToken(input);

    if(!**input) {
        // Parse error.
        return;
    }

    exponent = readExponent(input);

    success = true;
}

/* Exponent => coefficient. */
std::map<int, int> readPolynomial(const char *input) {
    std::map<int, int> ret;

    bool success = true;

    while(success) {
        int coefficient, exponent;

        readTerm(&input, coefficient, exponent, success);

        if(success) {
            ret[exponent] = coefficient;
        }
    }

    return ret;
}

This would probably all go nicely in a class with some abstraction (e.g. read from a stream instead of a plain string).