Arboles de Expresiones

ARBOLES DE EXPRESIONES

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.

En la ilustración siguiente se muestra un ejemplo de una expresión y su representación en forma de un árbol de expresión. Las diferentes partes de la expresión tienen un color distinto para hacerlas coincidir con el nodo correspondiente del árbol de expresión. También se muestran los diferentes tipos de los nodos del árbol de expresión.

REGLAS PARA LA CONSTRUCCION DE ARBOLES DE EXPRESION

Para contruir el árbol de expresiones que represente nuestra expresión matemática es necesario construir primero la misma expresión pero en la notación polaca correspondiente y a partir de esta es que se construye el árbol. El algoritmo usado para transformar una expresión infija a prefija es explicado a continuación.

Sea A una expresión infija cualquiera, formada por operadores, paréntesis (izquierdos y derechos) y operandos, también se usará una pila para los operadores. El procedimiento seguido es el siguiente:

Se lee un elemento de A, si este es un operador o un paréntesis izquierdo, entonces se actúa según la regla I y si es un operando entonces se envía directamente a la expresión de notación polaca. Si el elemento leído de A es un paréntesis derecho, entonces se desapilarán elementos de la pila de operadores hasta encontrar el correspodiente paréntesis izquierdo. Cada elemento desapilado pasa a formar parte de la notación polaca, excepto los paréntesis. Cuando no queden elementos en A, entonces se desapilan operadores de la pila, hasta que esta quede vacía.

Regla I:

Existe un orden de prioridad para los operadores, que de menor a mayor es el siguiente: suma (+) y resta (-), multiplicación (*) y división (/), exponenciación (^), operadores unarios. El paréntesis izquierdo lo trataremos como un operador (aunque no lo es) cuyo orden de prioridad es el mayor de todos cuando se quiera apilar y el menor de todos cuando esté en la cima de la pila.

Cuando se intente apilar algún operador se hará lo siguiente: si es un operador unario entonces se apila, si es un operador binario, se comparará su prioridad con el último insertado en la pila (el de la cima), si su prioridad es mayor, entonces se apilará. Si ocurre lo contrario (su prioridad es menor o igual) entonces el operador de la cima de la pila se desapilará y pasará a formar parte de la notación polaca. Se volverá a intentar apilar el operador siguiendo la misma regla, hasta que se pueda apilar, si la pila queda vacía también se apila. El paréntesis izquierdo siempre se apilará y no podrá ser desapilado por ningún operador y por tanto no formará parte de la notación polaca inversa.

El siguiente ejemplo, ayudará a entender mejor lo dicho anteriomente. Sea la siguiente expresión infija: 2^sin(y+x)–ln(x).
En la siguiente tabla se muestra paso a paso la conversión a notación postfija. Se usa el color rojo para señalar los casos en que es necesario desapilar operadores de la pila.

Construccion del árbol binario de expresiones

Una vez obtenida la expresión en notación postfija, se puede evaluar mediante el uso nuevamente de una pila. Sin embargo, en nuestro caso se trabaja con una árbol binario de expresiones, así que lo que se hace es construir el árbol. El algoritmo usado para construir el árbol no usa como tal la expresión postfija ya conformada, sino que el árbol se va construyendo usando las mismas reglas con las que se construye la notación postfija, una pila para los operadores y otra para los nodos del árbol, ambas no son necesitadas al terminar el árbol. El algoritmo es el siguiente:

Se siguen las mismas reglas expuestas anteriormente usando la pila de operadores, pero cuando se encuentra un operando o un operador es desapilado, entonces se crea el nodo correspondiente y se actúa según la regla II. Al finalizar el algoritmo solo debe quedar un nodo apilado en la pila de nodos, el que constituye el nodo raíz de nuestro árbol de expresiones.

Regla II.

Si el nodo corresponde a un operando, entonces se apila. Si el nodo corresponde a una operador unario entonces se desapila un nodo de la pila de nodos y es enlazado a la rama izquierda del nodo correspondiente al operador unario y este último es apilado. Si el nodo corresponde a un operador binario entonces dos nodos son desapilados de la pila de nodos, el primero es enlazado a la rama derecha del nodo binario y el segundo a la rama izquierda, nuevamente este nodo es apilado.

En el siguiente ejemplo se usa la misma expresión infija anterior (2^sin(y+x) – ln (x)) para ilustrar el procedimiento para construir el árbol:

Recorrido en preorden

En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.

En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

void preorden(tArbol *a)

{

  if (a != NULL) {

    tratar(a);                        //Realiza una operación en nodo

    preorden(a->hIzquierdo);

    preorden(a->hDerecho);

  }

}

Implementación en pseudocódigo de forma iterativa:

push(s,NULL);       //insertamos en una pila (stack) el valor NULL, para asegurarnos de que esté vacía

push(s,raíz);                       //insertamos el nodo raíz

MIENTRAS (s <> NULL) HACER

    p = pop(s);                     //sacamos un elemento de la pila

    tratar(p);                      //realizamos operaciones sobre el nodo p

    SI (D(p) <> NULL)               //preguntamos si p tiene árbol derecho

         ENTONCES push(s,D(p));

    FIN-SI

    SI (I(p) <> NULL)               //preguntamos si p tiene árbol izquierdo

         ENTONCES push(s,I(p));
FIN-SI