Resolviendo ecuaciones lineales representadas como una cadena.

algorithm expression-trees

Pregunta

Me dan una cadena 2*x + 5 - (3*x-2)=x + 5 y necesito resolver para x . Mi proceso de pensamiento es que lo convertiría en un árbol de expresiones, algo así como,

          =
        /  \
       -    +
      /\    /\
     +  -   x  5
    /\  /\ 
   *  5 * 2
  /\   /\
 2  x  3 x

Pero, ¿cómo puedo realmente reducir el árbol desde aquí? ¿Alguna otra idea?

Respuesta aceptada

Tienes que reducirlo utilizando axiomas del álgebra.

a * (b + c) -> (a * b) + (a * c)

Esto se hace verificando los tipos de cada nodo en el árbol de pases. Una vez que la cosa se haya expandido completamente en términos, puede verificar que sean realmente lineales, etc.

Los valores en el árbol serán variables o números. Sin embargo, no es muy bueno representarlas como clases heredadas de alguna clase AbstractTreeNode, porque cplusplus no tiene múltiples despachos. Así que es mejor hacerlo a la manera 'c'.

enum NodeType {
    Number,
    Variable,
    Addition //to represent the + and *
}

struct Node {
    NodeType type;
    //union {char*,  int, Node*[2]} //psuedo code, but you need
    //something kind of like this for the 
    //variable name ("x") and numerical value
    //and the children
}

Ahora puede consultar los tipos de un nodo y sus hijos utilizando el caso de cambio.

Como dije anteriormente, el código idiomático de c ++ usaría funciones virtuales pero carecería del envío múltiple necesario para resolver esto de manera limpia. (Necesitarías almacenar el tipo de todos modos)

Luego agrupas términos, etc. y resuelves la ecuación.

Puedes tener reglas para normalizar el árbol, por ejemplo

constant + variable -> variable + constant

Pondría x siempre a la izquierda de un término. Entonces x * 2 + x * 4 podría simplificarse más fácilmente

var * constant + var * constant -> (sum of constants) * var

En tu ejemplo ...

Primero, simplifique el '=' moviendo los términos (según la regla anterior)

El lado derecho será -1 * (x + 5), convirtiéndose en -1 * x + -1 * 5. El lado izquierdo será más difícil. Considere reemplazar a - b con a + -1 * b.

Finalmente,

2x + 5 + -3x + 2 + -x + -5 = 0

Entonces puedes agrupar los términos de la manera que quieras. (Escaneando a lo largo, etc)

(2 + -3 + -1) x + 5 + 2 + -5 = 0

Súmalos y cuando tengas mx + c, resuélvelo.


Respuesta popular

Suponiendo que la ecuación puede reducirse a f (x) = 0, y f (x) = a * x + b.

Puede transformar todas las hojas en el árbol de expresiones a f (x), por ejemplo: 2 -> 0 * x + 2, 3 * x -> 3 * x + 0, luego puede hacer operaciones aritméticas de f (x) en árbol de expresión. Finalmente resuelva la ecuación f (x) = 0.

Si la función es mucho más complicada que el polinomio, puede hacer una búsqueda binaria en x y usar el árbol de expresiones para calcular el lado izquierdo y derecho de la ecuación.



Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow