6.7. Árbol de análisis¶
Con la implementación de nuestra estructura de datos de árbol completa, miremos ahora un ejemplo de cómo puede usarse un árbol para resolver algunos problemas reales. En esta sección examinaremos los árboles de análisis. Los árboles de análisis se pueden usar para representar construcciones del mundo real como oraciones o expresiones matemáticas.
Figura 1: Un árbol de análisis para una oración simple¶
Figura 1: Un árbol de análisis para una oración simple
La Figura 1 muestra la estructura jerárquica de una oración simple. Representar una oración como una estructura de árbol nos permite trabajar con las partes individuales de la oración usando subárboles.
Figura 2: Árbol de análisis para \(((7+3)*(5-2))\)¶
Figura 2: Árbol de análisis para \(((7+3)*(5-2))\)
También podemos representar una expresión matemática como \(((7 + 3) * (5 - 2))\) como un árbol de análisis, tal como se muestra en la Figura 2. Ya hemos visto las expresiones completamente agrupadas, así que ¿qué sabemos acerca de esta expresión? Sabemos que la multiplicación tiene una mayor precedencia que la suma o la resta. Debido a los paréntesis, sabemos que antes de poder hacer la multiplicación debemos evaluar las expresiones de suma y resta que están entre paréntesis. La jerarquía del árbol nos ayuda a entender el orden de la evaluación para toda la expresión. Antes de poder evaluar la multiplicación del nivel superior, debemos evaluar la suma y la resta en los subárboles. La suma, que es el subárbol izquierdo, da un resultado de 10. La resta, que es el subárbol derecho, da 3. Usando la estructura jerárquica de los árboles, podemos simplemente reemplazar un subárbol completo con un nodo una vez que hemos evaluado las expresiones en los hijos. La aplicación de este procedimiento de sustitución nos da el árbol simplificado que se muestra en la Figura 3.
Figura 3: Un árbol de análisis simplificado para \(((7+3)*(5-2))\)¶
Figura 3: Un árbol de análisis simplificado para \(((7+3)*(5-2))\)
En lo restante de esta sección vamos a examinar los árboles de análisis en más detalle. En particular, veremos
Cómo crear un árbol de análisis a partir de una expresión matemática completamente agrupada.
Cómo evaluar la expresión almacenada en un árbol de análisis.
Cómo recuperar la expresión matemática original a partir de un árbol de análisis.
El primer paso en la construcción de un árbol de análisis es descomponer la cadena de la expresión en una lista de símbolos. Hay cuatro tipos diferentes de símbolos a considerar: paréntesis izquierdos, paréntesis derechos, operadores y operandos. Sabemos que cada vez que leamos un paréntesis izquierdo estaremos comenzando una nueva expresión, y por lo tanto debemos crear un nuevo árbol que corresponda a esa expresión. Por el contrario, cuando leamos un paréntesis derecho, habremos terminado una expresión. También sabemos que los operandos van a ser nodos hoja e hijos de sus operadores. Finalmente, sabemos que cada operador va a tener tanto un hijo izquierdo como un hijo derecho.
Usando la información anterior podemos definir cuatro reglas como sigue:
Si el símbolo actual es un
'(', agregar un nodo nuevo como hijo izquierdo del nodo actual y descender al hijo izquierdo.Si el símbolo actual está en la lista
['+', '-', '/', '*'], asignar al valor raíz del nodo actual el operador representado por el símbolo actual. Agregar un nuevo nodo como hijo derecho del nodo actual y descender al hijo derecho.Si el símbolo actual es un número, asignar dicho número al valor raíz del nodo actual y regresar al padre.
Si el símbolo actual es un
')', ir al padre del nodo actual.
Antes de escribir el código en Python, echemos un vistazo a un ejemplo de las reglas descritas anteriormente en acción. Usaremos la expresión \((3 + (4 * 5))\). Descompondremos esta expresión en la siguiente lista de símbolos de caracteres individuales ['(', '3', '+', '(', '4', '*', '5' ,')',')']. Inicialmente comenzaremos con un árbol de análisis que consiste en un nodo raíz vacío. La Figura 4 ilustra la estructura y el contenido del árbol de análisis, a medida que se procesa cada nuevo símbolo.
Figura 4: Seguimiento de la contrucción del aŕbol de análisis¶
Figura 4: Seguimiento de la contrucción del aŕbol de análisis
Utilizando la Figura 4, recorramos el ejemplo paso a paso:
Creamos un árbol vacío.
El primer símbolo leído es un (. Por la regla 1, creamos un nuevo nodo como hijo izquierdo de la raíz. Hacemos que el nodo actual sea este nuevo hijo.
El siguiente símbolo leído es un 3. Por la regla 3, asignamos el 3 al valor raíz del nodo actual y volvemos a subir el árbol al padre.
El siguiente símbolo leído es un +. Por la regla 2, asignamos el + al valor raíz del nodo actual y añadimos un nodo nuevo como hijo derecho. El nuevo hijo derecho se convierte en el nodo actual.
El siguiente símbolo leído es un (. Por la regla 1, creamos un nuevo nodo como hijo izquierdo del nodo actual. El nuevo hijo izquierdo se convierte en el nodo actual.
El siguiente símbolo leído es un 4. Por la regla 3, asignamos el 4 al valor raíz del nodo actual. Hacemos que el padre de 4 sea ahora el nodo actual.
El siguiente símbolo leído es un *. Por la regla 2, asignamos el * al valor raíz del nodo actual y creamos un nuevo hijo derecho. El nuevo hijo derecho se convierte en el nodo actual.
El siguiente símbolo leído es un 5. Por la regla 3, asignamos el 5 al valor raíz del nodo actual. Hacemos que el padre de 5 sea ahora el nodo actual.
El siguiente símbolo leído es un ). Por la regla 4 hacemos que el padre del * sea ahora el nodo actual.
El siguiente símbolo leído es un ). Por la regla 4 hacemos que el padre del + sea ahora el nodo actual. En este punto no hay padre para el + entonces hemos terminado.
A partir del ejemplo anterior, está claro que necesitamos realizar un seguimiento del nodo actual, así como del padre del nodo actual. La interfaz de la clase árbol binario nos proporciona una forma de obtener los hijos de un nodo, a través de los métodos obtenerHijoIzquierdo y obtenerHijoDerecho, pero ¿cómo podemos hacer un seguimiento de los padres? Una solución simple para mantener un registro de los padres a medida que recorremos el árbol es usar una pila. Siempre que deseemos descender a un hijo del nodo actual, primero incluimos el nodo actual en la pila. Cuando queramos regresar al padre del nodo actual, extraemos el padre de la pila.
Utilizando las reglas arriba descritas, junto con las operaciones de Pila y ArbolBinario, ahora estamos listos para escribir una función en Python para crear un árbol de análisis. El código para el constructor de nuestro árbol de análisis se presenta en el ActiveCode 1.
Las cuatro reglas para construir un árbol de análisis están codificadas como las primeras cuatro cláusulas de la instrucción if en las líneas 11, 15, 19 y 24 del ActiveCode 1. En cada caso, usted podrá ver que el código implementa la regla, como se ha descrito anteriormente, con unas pocas llamadas a los métodos de ArbolBinario o de Pila. La única comprobación de errores que hacemos en esta función está en la cláusula else en la que generamos una excepción ValueError si recibimos un símbolo de la lista que no reconocemos.
Ahora que hemos construido un árbol de análisis, ¿qué podemos hacer con él? Como primer ejemplo, escribiremos una función para evaluar el árbol de análisis, devolviendo el resultado numérico. Para escribir esta función, haremos uso de la naturaleza jerárquica del árbol. Fíjese de nuevo en la Figura 2. Recordemos que podemos reemplazar el árbol original por el árbol simplificado que se muestra en la Figura 3. Esto sugiere que podemos escribir un algoritmo que evalúa un árbol de análisis mediante la evaluación recursiva de cada subárbol.
Como hemos hecho con algoritmos recursivos anteriores, comenzaremos el diseño de la función de evaluación recursiva identificando el caso base. Un caso base natural para los algoritmos recursivos que operan sobre árboles es comprobar si hay un nodo hoja. En un árbol de análisis, los nodos hoja siempre serán operandos. Dado que los objetos numéricos como números enteros y de punto flotante no requieren más interpretación, la función evaluar puede simplemente devolver el valor almacenado en el nodo hoja. El paso recursivo que mueve la función hacia el caso base es llamar a evaluar sobre los hijos izquierdo y derecho del nodo actual. La llamada recursiva efectivamente nos mueve hacia abajo en el árbol, hacia un nodo hoja.
Para poner juntos los resultados de las dos llamadas recursivas, podemos aplicar simplemente el operador almacenado en el nodo padre a los resultados devueltos de la evalución de ambos hijos. En el ejemplo de la Figura 3 vemos que los dos hijos de la raíz se evalúan a sí mismos, es decir, 10 y 3. Aplicar el operador de multiplicación nos da un resultado final de 30.
El código para una función evaluar recursiva se muestra en el Programa 1. Primero, obtenemos referencias a los hijos izquierdo y derecho del nodo actual. Si la evaluación de tanto el hijo izquierdo como la del hijo derecho es None, entonces sabemos que el nodo actual es realmente un nodo hoja. Esta comprobación está en la línea 7. Si el nodo actual no es un nodo hoja, se busca el operador en el nodo actual y se aplica a los resultados de la evaluación recursiva de los hijos izquierdo y derecho.
Para implementar la aritmética, usamos un diccionario con las claves '+', '-', '*' y '/'. Los valores almacenados en el diccionario son funciones del módulo de operator de Python. El módulo operator nos proporciona las versiones funcionales de muchos operadores utilizados comúnmente. Cuando buscamos un operador en el diccionario, se recupera el objeto de función correspondiente. Dado que el objeto recuperado es una función, podemos llamarla de la manera usual funcion(parametro1, parametro2). Así que la búsqueda operadores['+'](2,2) es equivalente a operator.add(2,2).
Programa 1
def evaluar(arbolAnalisis):
operadores = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
hijoIzquierdo = arbolAnalisis.obtenerHijoIzquierdo()
hijoDerecho = arbolAnalisis.obtenerHijoDerecho()
if hijoIzquierdo and hijoDerecho:
fn = operadores[arbolAnalisis.obtenerValorRaiz()]
return fn(evaluar(hijoIzquierdo),evaluar(hijoDerecho))
else:
return arbolAnalisis.obtenerValorRaiz()
Finalmente, haremos un seguimiento a la función evaluar en el árbol de análisis que creamos en la Figura 4. Cuando llamamos a evaluar por primera vez, pasamos la raíz de todo el árbol como el parámetro arbolAnalisis. Luego obtenemos referencias a los hijos izquierdo y derecho para asegurarnos de que existan. La llamada recursiva tiene lugar en la línea 9. Comenzamos buscando el operador en la raíz del árbol, que es '+'. El operador '+' está asociado a la llamada de la función operator.add, que recibe dos parámetros. Como de costumbre para una llamada a una función en Python, lo primero que hace Python es evaluar los parámetros que se pasan a la función. En este caso ambos parámetros son llamadas recursivas a nuestra función evaluar. Usando evaluación de izquierda a derecha, la primera llamada recursiva va a la izquierda. En la primera llamada recursiva, la función evaluar recibe el subárbol izquierdo. Encontramos que el nodo no tiene hijos izquierdos o derechos, por lo que estamos en un nodo hoja. Cuando estamos en un nodo hoja simplemente devolvemos el valor almacenado en el nodo hoja como resultado de la evaluación. En este caso devolvemos el número entero 3.
En este punto tenemos un parámetro evaluado para nuestra llamada del nivel superior a operator.add. Pero todavía no hemos terminado. Continuando la evaluación de izquierda a derecha de los parámetros, ahora hacemos una llamada recursiva para evaluar el hijo derecho de la raíz. Encontramos que el nodo tiene tanto un hijo izquierdo como un hijo derecho, así que buscamos el operador almacenado en este nodo, '*', y llamamos a esta función usando los hijos izquierdo y derecho como parámetros. En este punto usted puede ver que ambas llamadas recursivas serán a los nodos hoja, cuyas evaluaciones corresponden a los enteros cuatro y cinco respectivamente. Con los dos parámetros evaluados, devolvemos el resultado de operator.mul(4,5). En este punto hemos evaluado los operandos para el operador '+' del nivel superior y todo lo que queda por hacer es terminar con la llamada a operator.add(3,20). El resultado de la evaluación de todo el árbol de la expresión \((3 + (4 * 5))\) es 23.