ÁRBOLES DE EXPRESION

Un árbol de expresión sirve para evaluar expresionesdel tipo:

(a+b)*c/d

Para que un árbol represente una expresión se deben tomar en cuenta 2 características muy importantes:

• Cualquier hoja está etiquetada sólo con un operando.

• Cualquier nodo interior n está etiquetado por un operador.

Por ejemplo, para representar una expresion el arbolquedaria como sigue:

a+(b-c)*d/c

+

/a

c*

- d

cb

Otro ejemplo:

(a+b)*(c+d)*

++

a b d c

Al introducir la expresión debemos de tomar en cuenta las siguientes características:

La raíz siempre debe ser un operador Las hojas siempre deben ser operandos Los nodos deben estar etiquetados por operadores Si un operador tiene mayor prioridad que la raiz se

coloca como hijo. Si un operador tiene igual o menor prioridad que un

nodo se coloca como padre. Un nodo puede contener como hijo otro subarbol que

contiene un pequeña expresion.

En los árboles de expresión, la sucesión del preorden de etiquetas nos da lo que se conoce como la forma prefijo de una expresión

Análogamente, la sucesión postorden de las etiquetas de un árbol expresión nos da lo que se conoce como la representación postfijo de una expresión

Finalmente, el inorden de una expresión en un árbol de expresión nos da la expresión infijo en sí misma, pero sin paréntesis

CONSTRUCCION DE UN ARBOL DE EXPRESION

Agoritmo:Mientras carácter diferente de nuloLeer carácter de la listaSi es paréntesis pasar al siguiente carácterCrear un nodo nuevo que contenga ese carácterSi el carácter que tiene nuevo es un:Operando

si el árbol esta vacío hacer raíz a nuevosi no recorrer el árbol por la derecha hasta llegar a un nodo con hojas

si la hoja izquierda, no esta etiquetada colocar operandosi no colocarlo en la hoja derecha.

Operadorsi la raíz es un operando

insertar nuevo en ese nodo, y convertir el operandoen el hijo izq.

si nosi hay un paréntesis abierto

insertar nuevo en la ultima hoja derecha y colocar operandocomo hijo izquierdo

Si no se cumple ninguna de las condiciones anterioressi la raíz es de igual prioridad o menor prioridad

convertir la raíz en el hijo izq. de nuevoelsesi la prioridad del nodo raíz es mayor al de nuevoinsertar nuevo como hijo derecho y colocar el nodo reemplazadocomo hijo izquierdo.

si el carácter anterior es paréntesis izquierdosi el sig. carácter es paréntesis derecho

si solo hay un operador en el árbolnuevo se convierte en raíz

si nose inserta en el ultimo nodo derecho, y el nodo se convierte en hijo izquierdo.

EVALUACION DE UN ARBOL DE EXPRESIÓN

Para que un árbol de expresión sea evaluado cada nodo debe ser declarado como sigue:

# define OPERADOR 0# define OPERANDO 1struct nodarbol{ short int tipo; //OPERADOR U OPERANDO// union{ char operador[10]; float val;}info;struct nodarbol *izq;struct nodarbol *der;};

typedef nodarbol *NODEPTR;

Debido a que un nodo puede contener información que es un numero (operando) o una cadena de caracteres (operador), la parte de información del nodo es un componente de union de la estructura.

Para realizar la función evalúa necesitamos de una función que denominaremos apply(p), la cual acepta un apuntador a un árbol de expresión que contiene un operador único y sus operándos numéricos, y retorna el resultado de aplicar el operador a sus operándos.

La función evalua servirá para que reciba un apuntador a un árbol de expresión y sustituye el árbol con un nodo de árbol que contiene el resultado numérico de la evaluación de la expresión.

void evalua(NODEPTR raiz){ float value; NODEPTR aux; evalua(aux->izq);

evalua(aux->der);apply(aux);

}

Función evalua

La función evalúa árbol quedaría;

float evalarbol(NODEPTR raiz){

evalua(raiz);

return (raiz->val);

free(raiz);

}