Aufbau eines Computeralgebrasystems

Question

Ich erstelle ein CAS (Computer Algebra System) in PHP, stecke aber gerade fest.Ich verwende diese Website .

Jetzt habe ich einen Tokenizer geschrieben.Eine Gleichung wie folgt wird konvertiert:

1+2x-3*(4-5*(3x))

dazu:

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

(wobei Gruppe ein weiterer Satz von Token ist).Wie kann ich diese Gleichung vereinfachen?Ja, ich weiß, was Sie tun können: X-Vars hinzufügen, aber sie gehören zur Untergruppe.Was ist die beste Methode, mit der ich mit diesen Token umgehen kann?

Answer 1

Ein wirklich nützlicher nächster Schritt wäre das Erstellen eines Analysebaums:

Sie würden eine davon erstellen, indem Sie einen Infix-Parser schreiben. Sie können dies entweder tun, indem Sie einen einfachen Parser für rekursiven Abstieg schreiben oder indem Sie die großen Waffen und mit einem Parser-Generator . In beiden Fällen hilft es, eine formale Grammatik zu erstellen:

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

primary: variable
       | number
       | '(' expression ')'

Beachten Sie, dass diese Grammatik nicht die 2x-Syntax verarbeitet, aber einfach hinzuzufügen sein sollte.

Beachten Sie die clevere Verwendung der Rekursion in den Grammatikregeln. primary erfasst nur Variablen, Zahlen und Ausdrücke in Klammern und stoppt, wenn es auf einen Operator stößt. multiplicative analysiert einen oder mehrere primary-Ausdrücke, die durch *-Zeichen begrenzt sind, stoppt jedoch, wenn sie auf ein +- oder --Zeichen stoßen. additive analysiert einen oder mehrere multiplicative-Ausdrücke, die durch + und - begrenzt sind, stoppt jedoch, wenn ein ) auftritt. Daher bestimmt das Rekursionsschema die Priorität des Operators.

Es ist nicht allzu schwierig, einen Predictive Parser von zu implementieren Hand, wie ich unten getan habe ( siehe vollständiges Beispiel auf ideone.com ):

function parse()
{
    global $tokens;
    reset($tokens);
    $ret = parseExpression();
    if (current($tokens) !== FALSE)
        die("Stray token at end of expression\n");
    return $ret;
}

function popToken()
{
    global $tokens;
    $ret = current($tokens);
    if ($ret !== FALSE)
        next($tokens);
    return $ret;
}

function parseExpression()
{
    return parseAdditive();
}

function parseAdditive()
{
    global $tokens;

    $expr = parseMultiplicative();

    for (;;) {
        $next = current($tokens);
        if ($next !== FALSE && $next->type == "operator" &&
            ($next->op == "+" || $next->op == "-"))
        {
            next($tokens);
            $left = $expr;
            $right = parseMultiplicative();
            $expr = mkOperatorExpr($next->op, $left, $right);
        } else {
            return $expr;
        }
    }
}

function parseMultiplicative()
{
    global $tokens;

    $expr = parsePrimary();

    for (;;) {
        $next = current($tokens);
        if ($next !== FALSE && $next->type == "operator" &&
            $next->op == "*")
        {
            next($tokens);
            $left = $expr;
            $right = parsePrimary();
            $expr = mkOperatorExpr($next->op, $left, $right);
        } else {
            return $expr;
        }
    }
}

function parsePrimary()
{
    $tok = popToken();
    if ($tok === FALSE)
        die("Unexpected end of token list\n");
    if ($tok->type == "variable")
        return mkVariableExpr($tok->name);
    if ($tok->type == "number")
        return mkNumberExpr($tok->value);
    if ($tok->type == "operator" && $tok->op == "(") {
        $ret = parseExpression();
        $tok = popToken();
        if ($tok->type == "operator" && $tok->op == ")")
            return $ret;
        else
            die("Missing end parenthesis\n");
    }

    die("Unexpected $tok->type token\n");
}

Okay, jetzt haben Sie diesen schönen Analysebaum und sogar ein hübsches Bild dazu. Was jetzt? Ihr Ziel (vorerst) könnte es sein, Begriffe einfach zu kombinieren, um ein Ergebnis des Formulars zu erhalten:

n1*a + n2*b + n3*c + n4*d + ...

Ich überlasse Ihnen diesen Teil. Ein Analysebaum sollte die Dinge viel einfacher machen.

Answer 2

PHP ist gut in Strings, Zahlen und Arrays. Aber es ist eine schlechte Sprache für die Implementierung der Manipulation symbolischer Formeln, da es keine native Maschinerie für die Verarbeitung von "symbolischen Ausdrücken" gibt, für die Sie wirklich Bäume wollen. Ja, Sie können all diese Maschinen implementieren. Schwieriger ist es, die algebraischen Manipulationen durchzuführen. Es ist ziemlich viel Arbeit, wenn Sie etwas halb anspruchsvolles bauen wollen. Idealerweise möchten Sie, dass Maschinen Ihnen helfen, die Transformationen direkt und einfach zu schreiben.

Wie werden Sie beispielsweise beliebige Algebra-Regeln implementieren? Assoziativität und Kommutativität? Begriff "Matching in einer Entfernung", z

  (3*a+b)-2(a-b)+a ==> 3a-b

Mit unserem ein einfaches CAS implementiert werden kann a href="http://www.semanticdesigns.com/Products/DMS/ProgramTransformation.html" rel="nofollow"> DMS-Programmtransformationssystem . In DMS sind harte mathematische Konstrukte wie Kommutativität und Assoziativität integriert, und Sie können Algebra-Regeln explizit schreiben, um mit symbolischen Formeln zu arbeiten.

Answer 3

Das Buch Computeralgebra und symbolische Berechnung: Mathematische Methoden von Joel S. Cohen beschreibt einen Algorithmus zur automatischen Vereinfachung algebraischer Ausdrücke.

Dieser Algorithmus wird in der Computeralgebra-Bibliothek Symbolism für C # verwendet.Gehen Sie zu Ihrem Beispiel mit dem folgenden C # -Programm über:

var x = new Symbol("x");

(1 + 2 * x - 3 * (4 - 5 * (3 * x)))
    .AlgebraicExpand()
    .Disp();

zeigt an der Konsole Folgendes an:

-11 + 47 * x