Construyendo un sistema de álgebra computarizada

Question

Estoy creando un CAS (Sistema de Álgebra Computacional) en PHP, pero estoy atascado ahora mismo. Estoy usando this website.

Ahora escribí un tokenizador. Será 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 el 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

Una muy útil siguiente paso sería construir un árbol de análisis:

Se podría hacer una de estas escribiendo un analizador infija. Usted puede hacer esto escribiendo un analizador sintáctico de descenso recursivo simple, o trayendo las armas grandes y using a parser generator. En cualquiera de los casos, 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 2x, pero debe ser fácil de añadir.

Observe el uso inteligente de recursividad en las reglas de la gramática. primary solo captura variables, números y expresiones entre paréntesis, y se detiene cuando se ejecuta en un operador. multiplicative análisis sintáctico de una o más expresiones delimitadas por primary* señales, pero se detiene cuando se encuentra con un signo + o -. additive análisis sintáctico de una o más multiplicative expresiones delimitadas por + y -, pero se detiene cuando se ejecuta en un ). Por lo tanto, el esquema de recursión determina la precedencia del operador.

No es tan terriblemente difícil implementar un predictive parser a mano, como lo he hecho a continuación (see full example at 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 usted tiene este precioso árbol de análisis, e incluso una muy imagen para ir con eso. ¿Ahora que?Su objetivo (por ahora) podría ser simplemente combinar términos de obtener un resultado de la forma:

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

voy a dejar esa parte de ti. 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. Idealmente, desea maquinaria que lo ayude a escribir las transformaciones de forma directa y sencilla.

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

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

Puede buscar la forma a simple CAS can be implemented utilizando nuestro DMS program transformation system. DMS tiene construcciones matemáticas duras como conmutatividad y asociatividad integradas, y usted puede escribir reglas de álgebra explícitamente para operar en fórmulas simbólicas.

Answer 3

El libro Computer Algebra and Symbolic Computation: Mathematical Methods by Joel S. Cohen describe un algoritmo para la simplificación automática de expresiones algebraicas.

Este algoritmo se utiliza en la biblioteca de álgebra computacional Symbolism para C#. Ir con su ejemplo, el siguiente programa en 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