Construire un système d'algèbre informatique

Question

Je crée un CAS (Système d'algèbre informatique) en PHP, mais je suis coincé en ce moment. j'utilise ce site Web.

Maintenant, j'ai écrit un tokenzer. Il convertira une équation comme celle-ci:

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

pour ça:

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

(où le groupe est un autre ensemble de jetons). Comment puis-je simplifier cette équation? Oui, je sais ce que vous pouvez faire: l'ajout de X-Vars, mais ils sont dans le sous-groupe. Quelle est la meilleure méthode que je puisse utiliser pour gérer ces jetons?

Answer 1

Une prochaine étape vraiment utile serait de construire un arbre d'analyse:

Vous en feriez un en écrivant un analyseur d'infixe. Vous pouvez soit faire cela en écrivant un analyseur de descente récursif simple, soit en apportant les gros canons et Utilisation d'un générateur d'analyseur. Dans les deux cas, il aide à construire une grammaire formelle:

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

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

Notez que cette grammaire ne gère pas le 2x Syntaxe, mais il devrait être facile à ajouter.

Remarquez l'utilisation intelligente de la récursivité dans les règles de grammaire. primary Capture uniquement les variables, les nombres et les expressions entre parenthèses, et s'arrête lorsqu'il se heurte à un opérateur. multiplicative analyses un ou plusieurs primary expressions délimitées par * signes, mais s'arrête quand il se heurte à un + ou - pancarte. additive analyses un ou plusieurs multiplicative expressions délimitées par + et -, mais s'arrête quand il se heurte à un ). Par conséquent, le schéma de récursivité détermine la priorité de l'opérateur.

Il n'est pas trop difficile de mettre en œuvre un analyseur prédictif à la main, comme je l'ai fait ci-dessous (Voir l'exemple complet sur 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");
}

D'accord, alors maintenant vous avez ce charmant arbre d'analyse, et même une jolie photo pour aller avec. Maintenant quoi? Votre objectif (pour l'instant) pourrait être simplement de combiner des termes pour obtenir le résultat du formulaire:

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

Je vais vous laisser cette partie. Avoir un arbre d'analyse devrait rendre les choses beaucoup plus simples.

Answer 2

PHP est bon en chaînes, chiffres et tableaux. Mais c'est un langage médiocre pour mettre en œuvre la manipulation de la formule symbolique, car il n'a pas de machinerie native pour traiter les "expressions symboliques", pour lesquelles vous voulez vraiment des arbres. Oui, vous pouvez implémenter toutes ces machines. Ce qui est plus difficile, c'est de faire les manipulations algébriques. C'est beaucoup de travail si vous voulez faire quelque chose de semi-sophistiqué. Idéalement, vous voulez que des machines vous aident à écrire les transformations directement et facilement.

Par exemple, comment allez-vous mettre en œuvre des règles arbitraires d'algèbre? Associativité et commutativité? Terme "correspondance à une distance"?, Par exemple

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

Vous pouvez regarder comment Un CAS simple peut être implémenté en utilisant notre Système de transformation du programme DMS. DMS a des constructions mathématiques dures comme la commutativité et l'association intégrées, et vous pouvez écrire des règles d'algèbre explicitement pour fonctionner sur des formules symboliques.

Answer 3

Le livreAlgèbre informatique et calcul symbolique: méthodes mathématiques de Joel S. CohenDécrit un algorithme pour la simplification automatique des expressions algébriques.

Cet algorithme est utilisé dans le Symbolisme Bibliothèque d'algèbre informatique pour C #. En allant avec votre exemple, le programme C # suivant:

var x = new Symbol("x");

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

Affiche ce qui suit sur la console:

-11 + 47 * x