Arboles de Expresió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.

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.

- 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.

----Construcción de un árbol de expresión----

Algoritmo

- 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.

------Operando---------

Si el árbol está vacío hacer raíz de 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 izquierdo, 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 anteriores si la raíz es de igual prioridad o menor prioridad convertir la raíz en el hijo izquierdo de nuevo si no la prioridad del nodo raíz es mayor al de nuevo insertar nuevo como hijo derecho y colocar el nodo reemplazado como hijo izquierdo.

-------------------------------------------------------------------------------------------------------------------------

Los árboles de expresión binaria es un árbol binario cuyas hojas son operandos, como constantes o nombres de variables, y los otros nodos contienen operadores.

Por ejemplo, la notación sufija a b + c d e + * * da como resultado el siguiente árbol de expresión. La notación de infijo correspondiente es (a+b)*(c*(d+e)) que se puede producir atravesando el árbol de expresión en un moda en orden. Sin embargo, se debe agregar un paréntesis de apertura y cierre al principio y al final de cada expresión (cada subárbol representa una subexpresión).

La construcción del árbol de expresiones se lleva a cabo leyendo la expresión del sufijo un símbolo a la vez. Si el símbolo es un operando, se crea un nuevo nodo de árbol binario y su puntero se coloca en un stack. Si el símbolo es un operador, los punteros a dos árboles, x y y, se extraen de la stack, y un nuevo árbol cuya raíz es el operador y cuyos hijos izquierdo y derecho apuntan a y y x, respectivamente se forma. Luego, se empuja un puntero a este nuevo árbol a la stack. Al final, un puntero al árbol de expresión completo permanece en la stack.