20.3. Árboles de expresión

Un árbol es un forma natural de representar la estructura de una expresión.
Al contrario que otras notaciones, puede representar el calculo de forma no
ambigua. Por ejemplo, la expresión infija 1 + 2 * 3 es ambigua a no ser que
sepamos que la multiplicación se realiza antes que la suma.

Este árbol de expresión representa el mismo calculo:

Sin título

 

Los nodos de un árbol de expresión pueden ser operandos como 1 y 2 u operado-
res como + y *. Los operandos son nodos hojas; los nodos operadores contienen
referencias a sus operandos. (Todos estos operadores son binarios, lo que sig-
nifica que tienen exactamente dos operandos.)Así podemos construir este árbol:

1: >>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3)))



Mirando la figura, no hay duda del orden de las operaciones; la multiplicación
se realiza antes para calcular el segundo operando de la suma.


Los arboles de expresión tienen muchos usos. El ejemplo de este capítulo usa
arboles para traducir expresiones a postfijo, prefijo e infijo. Arboles similares se
usan dentro de los compiladores para analizar, optimizar y traducir programas.

0