Arboles De Expresion

Arboles de expresión

Definición

Los árboles de expresiones representan el código de nivel del lenguaje en forma de datos. Los datos se almacenan en una estructura con forma de árbol. Cada nodo del árbol de expresión representa una expresión, por ejemplo, una llamada al método o una operación binaria, como x < y.

El código representado en árboles de expresión se puede compilar y ejecutar. Esto permite realizar cambios dinámicos en el código ejecutable.

Los árboles de expresión deben ser inmutables. Esto significa que, si desea modificar un árbol de expresión, deberá construir un nuevo árbol de expresión copiando el ya existente y reemplazando los nodos que hay en él. Puede usar un visitante de árbol de expresión para recorrer el árbol de expresión existente.

¿Para qué sirven?

Un árbol de expresión sirve para evaluar expresiones del tipo:

(a+b)*c/d

Para que un árbol represente una expresión se deben tomar en cuenta 2 características muy importantes:

• Cualquier hoja está etiquetada sólo con un operando.

• Cualquier nodo interior n está etiquetado por un operador.

Al introducir la expresión debemos de tomar en cuenta las siguientes características:

 La raíz siempre debe ser un operador

 Las hojas siempre deben ser operandos

 Los nodos deben estar etiquetados por operadores

 Si un operador tiene mayor prioridad que la raíz se coloca como hijo.

 Si un operador tiene igual o menor prioridad que un nodo se coloca como padre.

 Un nodo puede contener como hijo otro subárbol que contiene una pequeña expresión.

En los árboles de expresión, la sucesión del preorden de etiquetas nos da lo que se conoce como la forma prefijo de una expresión.

Análogamente, la sucesión postorden de las etiquetas de un árbol expresión nos da lo que se conoce como la representación postfijo de una expresión.

Finalmente, el inorden de una expresión en un árbol de expresión nos da la expresión infijo en sí misma, pero sin paréntesis.

Los árboles de expresión también se usan en Dynamic Language Runtime (DLR) para proporcionar interoperabilidad entre los lenguajes dinámicos y .NET Framework y, asimismo, para permitir que los programadores de compiladores emitan árboles de expresión en lugar de Lenguaje intermedio de Microsoft (MSIL). Para más información sobre DLR.

Ejemplos

Por ejemplo, para representar una expresión el árbol quedaría como sigue:

A + (b – c) * d / c

(a + b) * (c + d)

Construcción de un árbol de expresión

Mientras carácter diferente de nulo

Leer carácter de la lista

Si es paréntesis pasar al siguiente carácter

Crear un nodo nuevo que contenga ese carácter

Si el carácter que tiene nuevo es un:

Operando

Si el árbol está vacío hacer raíz a nuevo

Si no recorrer el árbol por la derecha hasta llegar a un nodo con hojas

Si la hoja izquierda, no está etiquetada colocar operando

Si no colocarlo en la hoja derecha.

Operador

Si la raíz es un operando

Insertar nuevo en ese nodo, y convertir el operando en el hijo izq.

Si no

Si hay un paréntesis abierto

Insertar nuevo en la última hoja derecha y colocar operando como hijo izquierdo

Si el carácter anterior es paréntesis izquierdo

Si el siguiente carácter es paréntesis derecho

Si solo hay un operador en el árbol

Nuevo se convierte en raíz

Si no

Se inserta en el último nodo derecho, y el nodo se convierte en hijo izquierdo.

Si no se cumple ninguna de las condiciones

...