Construindo um sistema de álgebra computacional

Question

Estou criando um CAS (Computer Algebra System) em PHP, mas estou preso no momento.Estou usando este site .

Agora eu escrevi um tokenizer.Ele converterá uma equação como esta:

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

para isso:

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

(onde grupo é outro conjunto de tokens).Como posso simplificar essa equação?Sim, eu sei o que você pode fazer: adicionar X-vars, mas eles estão no subgrupo.Qual é o melhor método que posso usar para lidar com esses tokens?

Answer 1

Uma próxima etapa realmente útil seria construir uma árvore de análise:

Você faria um desses escrevendo um analisador infixo. Você pode fazer isso escrevendo um analisador descendente recursivo simples ou trazendo grandes armas e usando um gerador de analisador . Em ambos os casos, ajuda a construir uma gramática formal:

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

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

Observe que esta gramática não lida com a sintaxe 2x, mas deve ser fácil de adicionar.

Observe o uso inteligente da recursão nas regras gramaticais. primary captura apenas variáveis, números e expressões entre parênteses e para quando atinge um operador. multiplicative analisa uma ou mais expressões primary delimitadas por sinais *, mas para quando encontra um + ou sinal -. additive analisa uma ou mais expressões multiplicative delimitadas por + e -, mas para quando atinge um ). Portanto, o esquema de recursão determina a precedência do operador.

Não é muito difícil implementar um analisador preditivo por lado a lado, como fiz abaixo ( veja o exemplo completo em 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, agora você tem esta adorável árvore de análise e até mesmo uma bela imagem para acompanhar. O que agora? Seu objetivo (por enquanto) pode ser simplesmente combinar os termos para obter um resultado do formulário:

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

Vou deixar essa parte para você. Ter uma árvore de análise deve tornar as coisas muito mais simples.

Answer 2

PHP é bom em strings, números e matrizes. Mas é uma linguagem pobre para implementar a manipulação de fórmulas simbólicas, porque não tem maquinário nativo para processar "expressões simbólicas", para as quais você realmente deseja árvores. Sim, você pode implementar todas essas máquinas. O mais difícil é fazer as manipulações algébricas . Dá muito trabalho se você quiser construir algo semi-sofisticado. O ideal é que você queira máquinas para ajudá-lo a escrever as transformações de maneira direta e fácil.

Por exemplo, como você implementará regras de álgebra arbitrárias? Associatividade e comutatividade? Termo "correspondência à distância" ?, por exemplo,

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

Você pode ver como um CAS simples pode ser implementado usando nosso < a href="http://www.semanticdesigns.com/Products/DMS/ProgramTransformation.html" rel="nofollow"> sistema de transformação de programa DMS . O DMS tem construções matemáticas difíceis, como comutatividade e associatividade, e você pode escrever regras de álgebra explicitamente para operar em fórmulas simbólicas.

Answer 3

O livro Álgebra Computacional e Computação Simbólica: Métodos Matemáticos de Joel S. Cohen descreve um algoritmo para simplificação automática de expressões algébricas.

Este algoritmo é usado na biblioteca de álgebra computacional Simbolismo para C #.Seguindo seu exemplo, o seguinte programa C #:

var x = new Symbol("x");

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

exibe o seguinte no console:

-11 + 47 * x