Costruire un sistema di computer algebra

Question

Sto creando un CAS (Computer Algebra System) in PHP, ma al momento sono bloccato.Sto utilizzando questo sito web .

Ora ho scritto un tokenizer.Convertirà un'equazione come questa:

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

a questo:

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

(dove il gruppo è un altro insieme di gettoni).Come posso semplificare questa equazione?Sì, so cosa puoi fare: aggiungere X-vars, ma sono nel sottogruppo.Qual è il metodo migliore che posso utilizzare per gestire questi token?

Answer 1

Un passo successivo veramente utile sarebbe costruire un albero di analisi:

Faresti uno di questi scrivendo un parser infisso. Puoi farlo scrivendo un semplice parser di discesa ricorsivo, o inserendo i grossi calibri e utilizzando un generatore di parser . In entrambi i casi, aiuta a costruire una grammatica formale:

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

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

Nota che questa grammatica non gestisce la sintassi 2x, ma dovrebbe essere facile da aggiungere.

Nota l'uso intelligente della ricorsione nelle regole grammaticali. primary acquisisce solo variabili, numeri ed espressioni tra parentesi e si interrompe quando si imbatte in un operatore. multiplicative analizza una o più espressioni primary delimitate da segni *, ma si interrompe quando incontra un segno + o -. additive analizza una o più espressioni multiplicative delimitate da + e -, ma si interrompe quando si imbatte in un ). Quindi, lo schema di ricorsione determina la precedenza degli operatori.

Non è troppo difficile implementare un parser predittivo di mano, come ho fatto di seguito ( vedi l'esempio completo su 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");
}

Ok, quindi ora hai questo adorabile albero sintetico e anche una bella immagine per accompagnarlo. E adesso cosa? Il tuo obiettivo (per ora) potrebbe essere semplicemente combinare i termini per ottenere un risultato del modulo:

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

Lascio questa parte a te. Avere un albero di analisi dovrebbe rendere le cose molto più semplici.

Answer 2

PHP è bravo con stringhe, numeri e array. Ma è un linguaggio scadente per implementare la manipolazione di formule simboliche, perché non ha un meccanismo nativo per elaborare "espressioni simboliche", per le quali si vogliono veramente alberi. Sì, puoi implementare tutti quei macchinari. Ciò che è più difficile è eseguire le manipolazioni algebriche . È un bel po 'di lavoro se vuoi costruire qualcosa di semi-sofisticato. Idealmente vuoi che i macchinari ti aiutino a scrivere le trasformazioni direttamente e facilmente.

Ad esempio, come implementerai regole di algebra arbitrarie? Associatività e commutatività? Termine "corrispondenza a distanza" ?, ad es.

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

Puoi vedere come un semplice CAS può essere implementato utilizzando il nostro < a href="http://www.semanticdesigns.com/Products/DMS/ProgramTransformation.html" rel="nofollow"> sistema di trasformazione del programma DMS . DMS ha costrutti matematici rigidi come la commutatività e l'associatività incorporate e puoi scrivere regole algebriche esplicitamente per operare su formule simboliche.

Answer 3

Il libro Computer Algebra e calcolo simbolico: metodi matematici di Joel S. Cohen descrive un algoritmo per la semplificazione automatica delle espressioni algebriche.

Questo algoritmo viene utilizzato nella libreria di algebra informatica Simbolismo per C #.Seguendo il tuo esempio, il seguente programma C #:

var x = new Symbol("x");

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

visualizza quanto segue sulla console:

-11 + 47 * x