ARBOLES DE EXPRESIÓN.

 

ARBOLES DE EXPRESIONES

 

a+b

 

 

                                                       

                                                                       (a+b)-(c-d)

                                         
                                                (a+b)-((c-d)+e)

              

                              Árboles de expresiones 

Los árboles de expresiones son estructuras de datos que definen código. Se basan en las mismas estructuras que usa un compilador para analizar el código y generar el resultado compilado.

Los árboles binarios se utilizan para almacenar expresiones aritméticas en memoria, esencialmente en compiladores de lenguajes de programación. Una expresión es una secuencia de tokens (componentes de léxicos que siguen unas reglas establecidas). Un token puede ser un operando o bien un operador.

Los paréntesis no se almacenan en el árbol pero están implicados en la forma del árbol, como puede apreciarse en la Figura

 
Un árbol de expresión es un árbol binario con las siguientes propiedades: 
1. Cada hoja es un operando. 
2. Los nodos raíz y los nodos internos son operadores. 
3. Los subárboles son subexpresiones cuyo nodo raíz es un operador.

 Los árboles binarios se utilizan para representar expresiones en memoria, esencialmente en compiladores de lenguajes de programación. Se observa que los paréntesis de la expresión no aparecen en el árbol, pero están implicados en su forma, y esto resulta muy interesante para la evaluación de la expresión. Si se supone que todos los operadores tienen dos operandos, se puede representar una expresión mediante un árbol binario cuya raíz contiene un operador y cuyos subárboles izquierdo y derecho son los operando izquierdo y derecho, respectivamente. Cada operando puede ser una letra (x, y, a, b, etc.) o una subexpresión representada como un subárbol. 

El nodo raíz del subárbol izquierdo contiene el operador (+) de la subexpresión izquierda y el nodo raíz del subárbol derecho contiene el operador (-) de la subexpresión derecha. Todos los operandos letras se almacenan en nodos hojas. 

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.