automatas unidad I

1.1Los árboles de expresiones
Un árbol de expresión sirve para evaluar expresiones
del 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.
Porejemplo, para representarunaexpresion el arbolquedariacomosigue:a+(b-c)*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 puedecontener como hijo otro subarbol que contiene una pequeña expresion.
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óninfija 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íadirectamente 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 quedevací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 lanotació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óninfija: 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 trabajacon 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....