ARBOLES DE EXPRESIONES (TEORÍA)
|
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
|
No hay comentarios:
Publicar un comentario