Version:0.9
StartHTML:0000000105
EndHTML:0000039743
StartFragment:0000000152
EndFragment:0000039709
/******************************************************/
/*************** Isidro Pastor Jorda ******************/
/******************************************************/
/****************** Telematica ************************/
/******************** FPII ****************************/
/****************** Practica 6 ************************/
/******************************************************/
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include "Pila.h"
#include "ArbolBinario.h"
#include <conio.c>
void Introducir(Pila &postfija, Valor &expresion);
int Prioridad(Valor op);
bool EsOperador(char aux);
void ArbolExpresion(Pila &Expresion, Arbol &arb);
int Evaluar(Arbol &a);
Valor Ensamblador(Arbol &a, int &i);
bool ArbolLleno(Arbol & a);
int ContarNodos(Arbol & a);
int Altura(Arbol & a);
int ContarHojas(Arbol & a);
int NodosInternos(Arbol & a);
void VerPrefija(Arbol & a);
void VerPostfija(Arbol & a);
void VerInfija(Arbol & a);
int main()
{
Valor expresion;
Pila postfija;
Arbol arb;
bool salir, salir_arbol;
salir = false;
int opcion, i;
clrscr();
cout << " Programa Practica 6 FP2 ITT Telematica \n";
cout << " Isidro Pastor Jorda\n";
while (!salir)
{
cout << "***********************Menu***********************" << endl;
cout << "1.Introducir la expresion:" << endl;
cout << "2.Visualizar en notacion prefija." << endl;
cout << "3.Visualizar en notacion infija." << endl;
cout << "4.Visualizar en notacion postfija." << endl;
cout << "5.Evaluar la expresion y mostrar el resultado" << endl;
cout << "6.Generar codigo emsamblador" << endl;
cout << "7.Menu arbol:" << endl;
cout << "8. Salir " << endl;
cout << "**************************************************" << endl;
cout << " Opcion -> ";
cin >> opcion;
switch (opcion)
{
case 1:
Introducir(postfija, expresion);
cout << " La expresion es -> " << expresion << endl;
ArbolExpresion(postfija,arb);
break;
case 2:
cout << " La expresion en notacion prefija es ";
VerPrefija(arb);
cout << endl;
break;
case 3:
cout << " La expresion en notacion infija es ";
VerInfija(arb);
cout << endl;
break;
case 4:
cout << " La expresion en notacion postfija es ";
VerPostfija(arb);
cout << endl;
break;
case 5:
cout << " Evaluacion de la expresion: " << expresion << " = " << Evaluar(arb) << endl;
break;
case 6:
i=0;
cout << " El codigo ensamblador generado es:" << endl;
Ensamblador(arb,i);
break;
case 7:
while (!salir_arbol)
{
clrscr(); // Borramos la pantalla
cout << " ********** Menu Arbol *******************" << endl;
cout << " 1. Altura del arbol" << endl;
cout << " 2. Numero de hojas del arbol" << endl;
cout << " 3. Numero de nodos del arbol" << endl;
cout << " 4. Numero de nodos internos del arbol" << endl;
cout << " 5. Verificacion de arbol lleno" << endl;
cout << " 6. Volver al Menu Principal " << endl;
cout << " *****************************************" << endl;
cout << " Elige opcion -> ";
cin >> opcion;
switch (opcion)
{
case 1:
cout << "La altura del arbol es: " << Altura(arb) << endl;
break;
case 2:
cout << "El arbol tiene " << ContarHojas(arb) << " hojas" << endl;
break;
case 3:
cout << "El arbol tiene " << ContarNodos(arb) << " nodos" << endl;
break;
case 4:
cout << "El arbol tiene " << NodosInternos(arb) << " nodos internos" << endl;
break;
case 5:
if(ArbolLleno(arb))
cout << "El arbol esta lleno." << endl;
else
cout << "El arbol no esta lleno." << endl;
break;
case 6:
salir_arbol = true;
break;
default:
cerr << "Opcion no valida";
break;
} // switch menu arbol
if (opcion != 6) // condicional para que no desaparezca la pantalla sin ver resultados
{
cin.ignore();
cout << " Pulsa return para continuar .... ";
cin.get();
}
}// while menu arbol
salir_arbol = false;
break;
case 8:
salir = true;
break;
default:
cerr << " Opcion no valida " << endl;
break;
}
if (!salir) // condicional para que no desaparezca la pantalla sin ver resultados
{
if (opcion != 1) // si hemos introducido una expresion el ignore lo hemos hecho antes
cin.ignore();
cout << " Pulsa return para continuar .... ";
cin.get();
}
clrscr();
} // while (!salir)
return 0;
};
/*****************************************************************************
* Funcion: Introducir
* Descripcion: Pedira al usuario que introduzca una expresion para introducirla
* en una pila en notacion postfija
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* postfija E/S Pila donde tendremos la expresion ordenada postfija
* expresion E/S Expresion introducida por el usuario para usarla en el programa principal
*
*
* Valor devuelto:
* No devuelve nada, void, pero modifica la pila y la expresion
*****************************************************************************/
void Introducir(Pila &postfija, Valor &expresion)
{
Pila b;
int i = 0;
Valor op, optop, num;
cin.ignore(); // Vaciamos el buffer para que podamos leer correctamente la expresion por si acaso
cout << "Introduce la expresion -> " ;
getline(cin, expresion);
while(expresion.find(' ')!= -1) // quitamos los espacios en blanco de la expresion
expresion.erase(expresion.find(' '),1);
while(i < expresion.length())
{
if (!EsOperador(expresion[i]) ) // si el caracter no es un operador
{ while(!EsOperador(expresion[i]) && (i < expresion.length()))// tendremos un numero mientras no sea operador y estemos dentro del string
{
num = num + expresion[i]; // vamos aņadiendo caracteres al numero
i++; // avanzamos el indice del string
}
postfija.Apilar(num); // apilamos en la pila postfija
num = ""; // reinicializamos el valor num para capturar nuevos numeros
}
else // Si el caracter leido no es un numero
{
op=expresion[i]; // almacenamos el caracter en op
b.CimaPila(optop); // leemos la cima de nuestra pila auxiliar
while(!b.PilaVacia() && (Prioridad(optop) >= Prioridad(op))) // si no es vacia y tiene mas prioridad la cima de pila
{
b.Desapilar(); // desapilamos de la pila auxiliar
postfija.Apilar(optop); // apilamos el operador en la pila postfija
b.CimaPila(optop); // y volvemos a leer la cima de la pila para seguir comparando
}
b.Apilar(op); // al final apilamos el dato leido del string
i++; // y aumentamos el indice del string
} // else
} // while
while (!b.PilaVacia()) // para finalizar desapilamos todo el contenido de la pila auxiliar
{
b.CimaPila(optop);
postfija.Apilar(optop); // y lo vamos apilando en la pila postfija
b.Desapilar();
}
return;
};
/*****************************************************************************
* Funcion: Prioridad
* Descripcion: Evaluacion de la prioridad de un operador
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* op E Operador del cual queremos saber la prioridad
*
*
*
* Valor devuelto:
* Un entero que sera la prioridad de ese operador
*****************************************************************************/
int Prioridad(Valor op)
{
int aux;
switch( int(op[0]) ) // asignamos una prioridad a los operadores
{
case 43:
case 45:
aux = 1;
break;
case 42:
case 47:
aux = 2;
break;
case 94:
aux = 3;
break;
default:
aux = 0;
break;
}
return(aux);
};
/*****************************************************************************
* Funcion: EsOperador
* Descripcion: Indica si el caracter pasado por valor es un operador o no
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* aux E Caracter que queremos identificar como operador o no
*
*
*
* Valor devuelto:
* true si el caracter es un operador, false en caso contrario
*****************************************************************************/
bool EsOperador(char aux)
{
bool ok;
/***************************************************************************
* si el caracter leido esta dentro del rango de numeros ascii comprendidos*
* 0 y 9 entonces entenderemos que NO es un operador, en caso contrario *
* consideraremos que el caracter es un operador *
***************************************************************************/
if( ( int(aux) >= int('0') ) && ( int(aux) <= int('9') ))
ok = false;
else
ok = true;
return(ok);
};
/*****************************************************************************
* Funcion: ArbolExpresion
* Descripcion: Pasa los datos de una pila que contiene una expresion en notacion
* postfija a un arbol binario para su mejor tratamiento
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* Expresion E/S Pila que contiene nuestra expresion en postfija
* arb E/S arbol que contendra la expresion
*
*
* Valor devuelto:
* Void, la funcion no devuelve en si ningun valor
*****************************************************************************/
void ArbolExpresion(Pila &Expresion, Arbol &arb)
{
Arbol i, d;
Valor s;
if ( !Expresion.PilaVacia())
{
Expresion.CimaPila(s); // iremos desapilando la pila para ir introduciendo los elementos en el arbol
Expresion.Desapilar();
if (EsOperador(s[0]))
{
ArbolExpresion(Expresion, d);
ArbolExpresion(Expresion, i);
}
arb.HacerArbol(i,s,d);
}
return;
};
/*****************************************************************************
* Funcion: Evaluar
* Descripcion: Evalua una expresion almacenada en un arbol binario
* realizando las operaciones necesarias para obtener el resultado
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S Arbol que contiene la expresion que queremos evaluar
*
*
*
* Valor devuelto:
* Devuelve un entero que sera el resultado de la expresion evaluada
*****************************************************************************/
int Evaluar(Arbol &a)
{
int aux = 0;
Valor x, operador;
int i; // contador
int op1, op2; //Variables auxiliares para almacenar resultados intermedios
if(!a.ArbolVacio())
{
if( a.HijoIzdo().ArbolVacio() && a.HijoDcho().ArbolVacio() )
{
a.Informacion(x);
i = 0;
while(i < x.length())
{
aux = aux + (int(x[i]) - int('0')); // pasamos a entero el char del numero leido
i++;
if(i < x.length())
aux = aux * 10; // si tenemos mas de un digito para el numero multiplicamos por 10 lo anterior
} //while
} //if
else
{
op1 = Evaluar(a.HijoIzdo()); // op1 sera el resultado de evaluar el hijo izquierdo recursivamente
op2 = Evaluar(a.HijoDcho()); // op2 sera el resultado de evaluar el hijo derecho recursivamente
a.Informacion(operador);
switch(int(operador[0])) // segun que operador sea haremos una operacion diferente
{
case 43:
aux = op1 + op2;
break;
case 45:
aux = op1 - op2;
break;
case 42:
aux = op1 * op2;
break;
case 47:
if (op2 == 0 )
cout << " Division por Cero, No se puede evaluar correctamente la expresion\n";
else
aux = op1 / op2;
break;
case 94:
aux = int (pow(op1, op2));
break;
default:
cerr << " Error de Operador no Reconocido -> " << operador << endl;
break;
}//switch
}//else
}// if(!a.ArbolVacio())
return(aux);
};
/*****************************************************************************
* Funcion: Ensamblador
* Descripcion: Genera y muestra por pantalla el codigo ensamblador de las
* operaciones que se deben realizar para evaluar la expresion
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Devolvera un Valor que sera el resultado de evaluar cada nodo del arbol
*****************************************************************************/
Valor Ensamblador(Arbol &a, int &i)
{
Valor aux, aux1, aux2, operador;
if (!a.ArbolVacio())
{
if ( ( ( a.HijoIzdo() ).ArbolVacio()) && ( ( a.HijoDcho() ).ArbolVacio() ) )
a.Informacion(aux);
else // cuando son nodos internos siempre tenemos operadores
{
aux1 = Ensamblador(a.HijoIzdo(), i);
aux2 = Ensamblador(a.HijoDcho(), i);
a.Informacion(operador);
i++;
cout.setf(ios::left);
cout.width (7);
switch (int(operador[0]))
{
case 43:
cout << "add \t \t";
break;
case 45:
cout << "sub \t \t";
break;
case 42:
cout << "mul \t \t";
break;
case 47:
cout << "div \t \t";
break;
case 94:
cout << "pow \t \t" ;
break;
default:
cerr << "error \t \t";
break;
}
cout << aux1 << "\t \t" << aux2 << "\t \t";
aux="temp";
aux= aux + char(48+i); // generamos una variable aleatoria para almacenar un resultado temporal
/************************************************************************
* Solo usamos 9 variables temporales, si se requieren mas se reutilizan*
* las variables empezando de nuevo por la 1 *
***********************************************************************/
if (i == 9) // iniciamos a cero de nuevo el valor de i cuando llevamos a 9
i = 0;
cout << aux << endl;
} // else
}
return (aux);
};
/*****************************************************************************
* Funcion: ArbolLleno
* Descripcion: La funcion comprueba si el arbol esta lleno
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S Arbol del que queremos saber si esta lleno o no
*
*
*
* Valor devuelto:
* true si el arbol esta lleno, false en caso contrario
*****************************************************************************/
bool ArbolLleno(Arbol & a)
{
int nodos, alt;
bool lleno;
nodos = ContarNodos(a);
alt = Altura(a);
lleno = (nodos == ( pow(2,alt) - 1 )); // 2^altura menos 1 son los nodos totales de un arbol
return (lleno);
};
/*****************************************************************************
* Funcion: ContarNodos
* Descripcion: Cuenta los nodos de un arbol
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S arbol del cual queremos contar los nodos
*
*
*
* Valor devuelto:
* Numero entero correspondiente al numero de nodos del arbol
*****************************************************************************/
int ContarNodos(Arbol & a)
{
int nodos = 0;
if (a.ArbolVacio()) // si el arbol es vacio tiene 0 nodos
nodos = 0;
else // si el arbol no es vacio contaremos los nodos del hijo izdo y del dcho + 1
{
nodos = nodos + ContarNodos(a.HijoIzdo());
nodos = nodos + ContarNodos(a.HijoDcho());
nodos++;
}
return (nodos);
};
/*****************************************************************************
* Funcion: Altura
* Descripcion: Funcion que calcula la altura de un arbol (numero de niveles)
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S Arbol del que queremos saber la altura
*
*
*
* Valor devuelto:
* Numero entero correspondiente a la altura del arbol
*****************************************************************************/
int Altura(Arbol & a)
{
int alt;
int der, izq;
if (a.ArbolVacio())
alt = 0;
else
{
izq = Altura (a.HijoIzdo());
der = Altura (a.HijoDcho());
if (izq > der)
alt = izq + 1;
else
alt = der + 1;
}
return (alt);
};
/*****************************************************************************
* Funcion: ContarHojas
* Descripcion: Cuenta las hojas o nodos terminales de un arbol
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S Arbol del que queremos contar las hojas
*
*
*
* Valor devuelto:
* Entero correspondiente al numero de hojas que tiene el arbol
*****************************************************************************/
int ContarHojas(Arbol & a)
{
int n_hojas = 0;
if (a.ArbolVacio())
n_hojas=0; // si el arbol es vacio no tenemos hojas
else
{
if ( (a.HijoIzdo().ArbolVacio()) && ( a.HijoDcho().ArbolVacio() ) )
n_hojas = 1; // si los dos hijos del arbol son vacios eso sera una hoja
else
n_hojas = ContarHojas(a.HijoIzdo()) + ContarHojas(a.HijoDcho()); // si el nodo no es vacio contamos y sumamos las hojas de sus hijos
}
return (n_hojas);
};
/*****************************************************************************
* Funcion: NodosInternos
* Descripcion: Funcion que cuenta los nodos internos de un arbol
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S Arbol del cual queremos contar los nodos internos
*
*
*
* Valor devuelto:
* Entero correspondiente a los nodos internos del arbol
*****************************************************************************/
int NodosInternos(Arbol & a)
{
int nodos, hojas;
nodos = ContarNodos(a);
hojas = ContarHojas(a);
return ( nodos - hojas ); // los nodos internos seran los nodos totales menos las hojas
};
/*****************************************************************************
* Funcion: VerPrefija
* Descripcion: Funcion que recorre el arbol de forma prefija y muestra el
* contenido de cada nodo de esta forma
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S Arbol que queremos visualizar
*
*
*
* Valor devuelto:
* No devuelve ningun valor, void, simplemente muestra el contenido por pantalla
*****************************************************************************/
void VerPrefija(Arbol &a)
{
Valor x;
if (!a.ArbolVacio())
{
a.Informacion(x); // mostramos el nodo raiz
cout << x << " ";
VerPrefija(a.HijoIzdo()); // y despues hijo izquierdo
VerPrefija(a.HijoDcho()); // seguido del hijo derecho
}
return;
};
/*****************************************************************************
* Funcion: VerPostfija
* Descripcion: Funcion que recorre el arbol de forma Postfija y muestra el
* contenido de cada nodo de esta forma
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S Arbol que queremos visualizar
*
*
*
* Valor devuelto:
* No devuelve ningun valor, void, simplemente muestra el contenido por pantalla
*****************************************************************************/
void VerPostfija(Arbol & a)
{
Valor x;
if (!a.ArbolVacio())
{
VerPostfija(a.HijoIzdo()); // mostramos primero el contenido del hijo izquierdo
VerPostfija(a.HijoDcho()); // despues el derecho
a.Informacion(x); // y finalmente el nodo raiz
cout << x << " ";
}
return;
};
/*****************************************************************************
* Funcion: VerInfija
* Descripcion: Funcion que recorre el arbol de forma Infija y muestra el
* contenido de cada nodo de esta forma
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* a E/S Arbol que queremos visualizar
*
*
*
* Valor devuelto:
* No devuelve ningun valor, void, simplemente muestra el contenido por pantalla
*****************************************************************************/
void VerInfija(Arbol & a)
{
Valor x;
if (!a.ArbolVacio())
{
VerInfija(a.HijoIzdo()); // mostramos primero el contenido del hijo izquierdo
a.Informacion(x); // despues el contenido del nodo raiz
cout << x << " ";
VerInfija(a.HijoDcho()); // y finalmente el contenido del hijo derecho
}
return;
};