Arboles

Evaluación de expresiones algebraicas con variables

En esta práctica procederemos a evaluar expresiones escritas en forma ‘infija’ (el operador está situado entre los operandos) con paréntesis y con operandos que serán ‘variables’ (cada vez que deseemos evaluar la expresión pediremos al usuario que nos dé los valores concretos de las variables para esa evaluación). Las operaciones válidas queevaluaremos serán las operaciones binarias ‘+’, ‘-‘, ‘*’, ‘/’.
Expresiones válidas a evaluar serán, por ejemplo: a + (b - c) / d, (a+b) / (c-d) * e,...
0. Objetivos
a. Utilización del tipo abstracto de datos ‘Arbol binario’.
b. Reutilización de código (reutilización de la clase ‘Pila’).
c. Utilización de código no desarrollado por el usuario (función ‘infija_a_posfija’ y clase‘TablaSimbolos”).
d. Trabajo con funciones recursivas.
1. INTRODUCCIÓN
Una manera adecuada de representar expresiones aritméticas es a través de los árboles binarios de expresiones. Esta representación retiene de manera natural la precedencia y la asociatividad de los operadores aritméticos.
En un árbol binario de expresiones cada nodo contiene la información de un elemento de la expresión (unoperando o un operador) y la propia estructura del árbol viene determinada por la forma de la expresión aritmética.
Un ejemplo de esto lo tenemos en los siguientes árboles de expresiones:
[pic]
Se puede ver que dependiendo de la colocación de los paréntesis se fuerza el cambio de precedencia de los operadores y las expresiones generan árboles distintos.
También es importanteresaltar que en el árbol claramente no son necesarios los paréntesis, ya que la precedencia en las operaciones viene dada por la estructura del árbol.
La evaluación de las expresiones, es decir, la obtención de su resultado, se consigue recorriendo el árbol de expresiones en forma postfija y realizando para cada nodo que contiene un operador dicha operación sobre sus hijos. De hecho, si examinamos elárbol en recorrido post-orden imprimiendo en pantalla el contenido de cada nodo, obtendremos lo que se denomina la expresión postfija de la expresión. Las expresiones postfijas de los árboles del ejemplo son las siguientes:
Para la expresión infija (2+5)*3+1, la expresión postfija es 2 5 + 3 * 1 +
Para la expresión infija 2+5*3+1, la expresión postfija es 2 5 3 * + 1 +
Nótese que la expresiónpostfija, al igual que ocurría en el árbol, no necesita utilizar paréntesis.
De la misma forma que podemos obtener la expresión postfija a partir del árbol de expresiones, también podemos hacer lo contrario, es decir, obtener el árbol de expresiones a partir de una expresión postfija. Este hecho va a ser utilizado en la presente práctica.
2. Realización de la práctica
a.- Obtención de laexpresión postfija y la tabla de variables.
El programa deberá empezar pidiendo la expresión aritmética en forma infija que deseamos evaluar.
Una vez guardada la expresión en una variable de tipo string pasaremos la expresión a su forma postfija y extraeremos de la expresión una tabla con las variables utilizadas en la expresión Utilizaremos para ello una función proporcionada por el profesor deprácticas ‘infijo_a_posfijo’. El prototipo de esta función es:
bool infijo_a_posfijo (string , string &, TablaSimbolos &);
Esta función tiene una entrada que es la cadena de la expresión infija.
Como salidas de la función tenemos tres valores (dos devueltos por referencia y uno como resultado de la función):
La primera salida (segundo parámetro de la función) es la cadena con la expresiónpostfija.
La segunda salida (tercer parámetro de la función) es un objeto de tipo TablaSimbolos que es la tabla donde se almacenan los identificadores correspondientes a los nombres de cada variable.
La tercera salida (valor devuelto por la función) es un valor booleano. La función devuelve ‘true’ si la expresión esta sintácticamente bien formada o ‘false’ si había algún error sintáctico en...