C ++ extrahieren Polynomkoeffizienten

Question

So habe ich ein Polynom, das wie folgt aussieht: -4X ^ 0 + x ^ 1 + 4x ^ 3 - 3x ^ 4
Ich kann diese tokenize durch Raum und '+' in: -4X ^ 0, x ^ 1, 4x ^ 3, -, 3 x ^ 4

Wie kann ich nur die Koeffizienten mit negativen Vorzeichen: -4, 1, 0, 4, -3
x ist die einzige Variable, und dies wird alle Tage erscheinen, um erscheint
in Planung der Koeffizienten in einem Array mit dem Array-Index ist der Exponent
Speicher so: -4 bei Index wäre 0, 1 bei Index 1, Index 0 bei 2, 4 mit dem Index 3, -3 bei Index 4

wäre

Answer 1

Wenn Sie Token aufgeteilt haben „-4X ^ 0“, „x ^ 1“ usw. können Sie strtol () verwenden, um die Textdarstellung in eine Zahl zu konvertieren. strtol wird auf den ersten Nichtziffernzeichen automatisch angehalten, so dass die ‚x‘ es stoppen; strtol geben Ihnen einen Zeiger auf das Zeichen, das es stoped, also wenn Sie paranoid sein wollen, können Sie die Zeichen überprüfen ist ein x.

Sie müssen implizite 1en behandeln (das heißt in "x ^ 1" speziell). Ich würde so etwas tun:

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

Answer 2

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: Einfache Methode, um die Koeffizienten zu erhalten (einschließlich Vorzeichen):

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 3

scannen die Zeichenfolge für eine ‚x‘, dann gehen Sie rückwärts jedes Zeichen des Koeffizienten zu speichern, bis Sie weißen Raum treffen. zB:

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 4

Für eine schnelle Lösung wäre mein Ansatz einen rekursiven Abstieg Parser zu schreiben. Verschieben Sie in der Zeichenfolge nach vorne und extrahieren Sie die Komponenten, die Sie wollen. Es gibt viele Beispiele um einen Parser eines Ausdrucks, wie dies für das Schreiben.

Wenn Sie eine Bibliothek verwenden möchten, können Sie boost :: regex verwenden oder :: Geist steigern, je nachdem, welche Art von Ansatz wollen Sie zu übernehmen.

Answer 5

Schreiben Sie einen einfachen tokenizer. Definieren einer Anzahl Token (/[-0123456789][0123456789]+/), einen Exponenten Token (/x^(::number::)/). Ignorieren Leerzeichen und +.

Kontinuierlich lesen Token, wie Sie sie bis zum Ende des Strings erwarten würden. Dann spuckte die Tokens in welcher Form auch immer Sie wollen (zum Beispiel ganze Zahlen).

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;
}

Dies würde wahrscheinlich alle schön in einer Klasse mit einem gewissen Abstraktion geht (zum Beispiel aus einem Stream gelesen anstelle einem einfachen String).