Construyendo un sistema de álgebra computacional

Question

Estoy creando un CAS (Computer Algebra System) en PHP, pero estoy atascado en este momento.Estoy usando este sitio web .

Ahora escribí un tokenizador.Convertirá una ecuación como esta:

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

a esto:

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

(donde grupo es otro conjunto de tokens).¿Cómo puedo simplificar esta ecuación?Sí, sé lo que puedes hacer: agregar X-vars, pero están en el subgrupo.¿Cuál es el mejor método que puedo usar para manejar esos tokens?

Answer 1

Un siguiente paso realmente útil sería construir un árbol de análisis:

Puede crear uno de estos escribiendo un analizador infijo. Puede hacer esto escribiendo un analizador de descenso recursivo simple o incorporando las armas grandes y usando un generador de analizador . En cualquier caso, ayuda a construir una gramática formal:

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

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

Tenga en cuenta que esta gramática no maneja la sintaxis de 2x, pero debería ser fácil de agregar.

Observe el uso inteligente de la recursividad en las reglas gramaticales. primary solo captura variables, números y expresiones entre paréntesis, y se detiene cuando se encuentra con un operador. multiplicative analiza una o más expresiones primary delimitadas por signos *, pero se detiene cuando se encuentra con un + o un signo -. additive analiza una o más expresiones multiplicative delimitadas por + y -, pero se detiene cuando se encuentra con un ). Por lo tanto, el esquema de recursividad determina la precedencia de los operadores.

No es demasiado difícil implementar un analizador predictivo mano, como he hecho a continuación ( ver el ejemplo completo en 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");
}

Bien, ahora tienes este hermoso árbol de análisis e incluso una bonita imagen para acompañarlo. ¿Ahora que? Su objetivo (por ahora) podría ser simplemente combinar términos para obtener un resultado del formulario:

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

Te dejo esa parte. Tener un árbol de análisis debería hacer las cosas mucho más sencillas.

Answer 2

PHP es bueno en cadenas, números y matrices. Pero es un lenguaje pobre para implementar la manipulación de fórmulas simbólicas, porque no tiene una maquinaria nativa para procesar "expresiones simbólicas", para las cuales realmente quieres árboles. Sí, puedes implementar toda esa maquinaria. Lo que es más difícil es hacer las manipulaciones algebraicas . Es bastante trabajo si quieres construir algo semi-sofisticado. Lo ideal es que desee maquinaria que le ayude a escribir las transformaciones de forma directa y sencilla.

Por ejemplo, ¿cómo implementará reglas de álgebra arbitrarias? ¿Asociatividad y conmutatividad? ¿Término "coincidencia a distancia" ?, por ejemplo,

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

Puede ver cómo se puede implementar un CAS simple con nuestro < a href="http://www.semanticdesigns.com/Products/DMS/ProgramTransformation.html" rel="nofollow"> sistema de transformación de programas DMS . DMS tiene construcciones matemáticas difíciles como conmutatividad y asociatividad incorporadas, y puede escribir reglas de álgebra explícitamente para operar en fórmulas simbólicas.

Answer 3

El libro Álgebra computacional y computación simbólica: métodos matemáticos por Joel S. Cohen describe un algoritmo para la simplificación automática de expresiones algebraicas.

Este algoritmo se utiliza en la biblioteca de álgebra informática Symbolism para C #.Siguiendo con su ejemplo, el siguiente programa C #:

var x = new Symbol("x");

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

muestra lo siguiente en la consola:

-11 + 47 * x