Pero lo que has vuelto a escribir, sólo tienes nuevo la declaración de notacion_infija(char) const, notacion_funcional() const y esExtendido() const, que son funciones miembro de la clase arbin, pero te falta su implementación. Pégamelas en otro mensaje y te ayudaré.

Enga saludos

Responder

Re: Re: Re: Arbol binario de expresiones c++

Enviado por kruncher el día 27 de mayo de 2008

Hola farenheit, aver esto es todo lo q tengo hecho de momento. Lo que necesito crear para continuar es la implementación recursiva de una funcion para crear un árbol binario según un string pasado como parámetro.

/********************/
/* arbin.h */
/********************/
#include <iostream>
using namespace std;

#ifndef ARBIN
#define ARBIN

template <class T>
class arbin {
public:
//constructoras
//construye un arbol binario vacio
arbin();

//crea un nuevo arbol binario a partir de un elemento y dos arboles binarios
arbin(const T & e, const arbin<T> & ai=arbin(), const arbin<T> & ad=arbin());

//modifica un arbin poniendo e como raiz e izqdo y dcho como hijo izquierdo
// y derecho respectivamente
void modificar (const T & e, const arbin<T> & izqdo, const arbin<T> & dcho);

//modica el arbol actual hasta obtener el arbin vacio
void vaciar();

//Copia el arbol binario actual
arbin<T> copiar();

//Devuelve el subarbol izquierdo del &#65533;rbol, NULL si est&#65533; vac
arbin<T> & izquierdo() const;

//Devuelve el subarbol derecho del &#65533;rbol, NULL si est&#65533; vac
arbin<T> & derecho() const;
//Devuelve el elemento de la raiz
const T & datoraiz() const;
T & datoraiz() ;

//Indica si el &#65533;rbol binario est&#65533; vacio
bool esvacio () const;

//recorre el arbol en preorden
void preorden() const;

//muestra el arbol en notacion infija
void notacion_infija(char) const;

//muestra el arbol en notacion infija
void notacion_funcional() const;

//Comprueba que el arbin es extendido
bool esExtendido () const;

..........................

Estas són las cabeceras d las funciones que tengo en esta clase, están todas implementadas. Ahora necesito crear un arbol binario desde el main recursivamente, según me ha explicado el profesor se crea mediante el constructor y la funcion de modificar.

Lo que tengo hecho yo en el main (q no funciona del todo) es esto:

/********************/
/* main.cpp */
/********************/
bool es_entero (char a) {
if (a=='*' || a=='/' || a=='-' || a=='+')
return false;
return true;
}

arbin <char> crear_arbol (char *s, int &pos){
int tam = strlen (s);
pos++;
if (es_entero(s[pos-1]))
return arbin <char> (s[pos]);
else
return arbin <char> (s[pos],crear_arbol(s,pos));
return arbin <char> (s[pos],crear_arbol(s,&pos+1));
}

int main () {
char s[] = "+3*45";
//char s[] = "*+26-71";
//char s[] = "/**9/82+15+43";
//char s[]="+-32*/15+-64*83";

arbin <char> a;
a = crear_arbol (s,0);

a.preorden (); // para mostrarlo
}

La funcion coge un string q se le pasa char s[] = "+3*45";
Crea un arbin con [+] y dos hijos, como el caracter actual es un [+] significa que el caracter siguiente [3] es el hijo izquierdo. El siguiente carácter [*] va después de un número, lo que significa q es el hijo derecho... no se me explico muy bien creo... el resultado tendria que ser así:

+
/ \
3 *
/ \
4 5

 

Responder

Re: Re: Re: Re: Arbol binario de expresiones c++

Enviado por kruncher el día 27 de mayo de 2008

<img src="http://www.google.es/intl/en_com/images/logo_plain.png">

 

Responder

Re: Re: Re: Re: Re: Arbol binario de expresiones c++

Enviado por kruncher el día 27 de mayo de 2008

No se insertar imágenes.... os dejo esta url con dibujos de arboles:

http://img221.imageshack.us/my.php?image=diagrama1...

 

Responder

SOLUCION

Ya tengo hecho el programa, gracias por la ayuda. Lo pego por si os interesa.

/********************************************/
/* arbin.h
/********************************************/
//Clase ARBOL BINARIO
//Esta la clase arbol binario recursiva con el nodo dentro

#include <iostream>
using namespace std;

#ifndef ARBIN
#define ARBIN

template <class T>
class arbin {
public:
//constructoras
//construye un arbol binario vacio
arbin();

//crea un nuevo arbol binario a partir de un elemento y dos arboles binarios
arbin(const T & e, const arbin<T> & ai=arbin(), const arbin<T> & ad=arbin());

//modifica un arbin poniendo e como raiz e izqdo y dcho como hijo izquierdo
// y derecho respectivamente
void modificar (const T & e, const arbin<T> & izqdo, const arbin<T> & dcho);

//modica el arbol actual hasta obtener el arbin vacio
void vaciar();

//Copia el arbol binario actual
arbin<T> copiar();

//Devuelve el subarbol izquierdo del &#65533;rbol, NULL si est&#65533; vac
arbin<T> & izquierdo() const;

//Devuelve el subarbol derecho del &#65533;rbol, NULL si est&#65533; vac
arbin<T> & derecho() const;
//Devuelve el elemento de la raiz
const T & datoraiz() const;
T & datoraiz() ;

//Indica si el &#65533;rbol binario est&#65533; vacio
bool esvacio () const;

//recorre el arbol en preorden
void preorden() const;

//muestra el arbol en notacion infija
string notacion_infija() const;

//Comprueba que el arbin es extendido
bool esExtendido () const;

private:
//nodo del arbol binario
struct Nodo {
T info;
arbin<T> izq;
arbin<T> der;

//constructor
Nodo (T e=T(), arbin<T> iz=arbin(), arbin<T> de=arbin()) {
info=e;
izq=iz;
der=de;
}
//destructor
//~Nodo();
};

typedef Nodo * PNodo;
PNodo raiz; //puntero a la raiz del &#65533;rbol binario

};
#endif

//IMPLEMENTACIONES
//construye un arbol binario vacio
template <class T>
arbin<T>::arbin() {
raiz=NULL;
}

//crea un nuevo arbol binario a partir de un elemento y dos arboles binarios
template <class T>
arbin<T>::arbin(const T & e, const arbin<T> & izqdo, const arbin<T> & decho) {
raiz= new Nodo(e, izqdo, decho);
}


//modifica un arbin poniendo e como raiz e izqdo y dcho como hijo izquierdo
// y derecho respectivamente
template <class T>
void arbin<T>::modificar (const T & e, const arbin<T> & izqdo, const arbin<T> & dcho) {
if (!esvacio()) {
raiz->info=e;
raiz->izq=izqdo;
raiz->der=dcho;
}
else cout << "Error: arbol binario vacio" << endl;
}
//modica el arbol actual hasta obtener el arbin vacio
template <class T>
void arbin<T>::vaciar() {
if (!esvacio()) {
izquierdo().vaciar();
derecho().vaciar();
delete raiz;
}
}


//Copia el arbol binario actual
template <class T>
arbin<T> arbin<T>::copiar() {
arbin i, d ;
if (!esvacio()) {
if (!izquierdo().esvacio()) i=izquierdo().copiar();
if (!derecho().esvacio()) d=derecho().copiar();
//raiz=new Nodo(raiz->info, i, d);
//return raiz;
arbin x (raiz->info, i, d);
return x;
}
}

//Devuelve el subarbol izquierdo del &#65533;rbol, NULL si est&#65533; vac
template <class T>
arbin<T> & arbin<T>::izquierdo() const {
return raiz->izq;
}

//Devuelve el subarbol derecho del &#65533;rbol, NULL si est&#65533; vac
template <class T>
arbin<T> & arbin<T>::derecho() const {
return raiz->der;
}
//Devuelve el elemento de la raiz
template <class T>
const T & arbin<T>::datoraiz() const {

return raiz->info;
}
template <class T>
T & arbin<T>::datoraiz() {
return raiz->info;
}


//Indica si el &#65533;rbol binario est&#65533; vacio
template <class T>
bool arbin<T>::esvacio () const {
return (raiz==NULL);
}

template <class T>
void arbin<T>::preorden() const {
if (!esvacio()) {
cout << raiz->info << " ";
izquierdo().preorden();
derecho().preorden();
}
}

template <class T>
string arbin<T>::notacion_infija()const
{
string st;
if(!esvacio())
{
if(!izquierdo().esvacio() && !derecho().esvacio())
return st="("+izquierdo().notacion_infija()+raiz->info+derecho().notacion_infija()+")";
else
return st=raiz->info;
}
}

////////////// OKk
template <class T>
bool arbin<T>::esExtendido() const {
bool ext=false;

if(esvacio()) {
ext=true;

} else {
if((!izquierdo().esvacio()) && (derecho().esvacio()) || ((izquierdo().esvacio())&& (!derecho().esvacio()))) {
ext=false;
} else {
ext=izquierdo().esExtendido();
ext=derecho().esExtendido();
}
}
return ext;
}

/********************************************/
/* main.cpp
/********************************************/
#include <iostream>
#include "arbin.h"
using namespace std;

bool es_entero (char a) {
if (a=='*' || a=='/' || a=='-' || a=='+')
return false;
return true;
}

float evaluar (const arbin<char> &a) {
if (a.izquierdo().esvacio() && a.derecho().esvacio()) {
return a.datoraiz() - '0';
} else {
switch (a.datoraiz()) {
case '+':
return (evaluar(a.izquierdo()) + evaluar(a.derecho()));
break;
case '-':
return (evaluar(a.izquierdo()) - evaluar(a.derecho()));
break;
case '*':
return (evaluar(a.izquierdo()) * evaluar(a.derecho()));
break;
case '/':
return (evaluar(a.izquierdo()) / evaluar(a.derecho()));
break;
}
}
}

arbin <char> crear_arbol2 (string cadena,int tam, int &pos){
arbin<char> izq,der;
if (pos<tam) {
if (!es_entero(cadena[pos])) {
arbin<char> arb(cadena[pos]);
pos++;
izq = crear_arbol2 (cadena,tam,pos);
pos++;
der = crear_arbol2 (cadena,tam,pos);
arb.modificar(arb.datoraiz(),izq,der);
return arb;
} else {
return arbin<char> (cadena[pos],izq,der);
}
}
}

void notacion_funcional(const arbin<char> & a){
char raiz;
if (!a.esvacio()) {
raiz=a.datoraiz();
switch (raiz) {
case '+':
cout << "suma(";
break;
case '-':
cout << "resta(";
break;
case '*':
cout << "producto(";
break;
case '/':
cout << "division(";
break;
default:
cout << raiz;
break;
}
notacion_funcional(a.izquierdo());
if(raiz=='+' || raiz=='*'|| raiz=='/'||raiz=='-' )
cout << ",";
notacion_funcional(a.derecho());
}
if(raiz=='+' || raiz=='*'|| raiz=='/'||raiz=='-' )
cout<<")";
}

int main () {

string s;
arbin <char> a;
char sig = 's';
int tam;

while (sig!='n') {
cout << "Nueva cadena: ";
cin >> s;
tam= s.length();
cout << endl;
cout << "Longitud: " << tam ;

// PREGUNTA 1
//cout << "****************************************" << endl;
//cout << "Crear arbol: " << endl;
int pos =0;
a = crear_arbol2 (s,tam,pos);
cout << endl;
// PREGUNTA 2
cout << "****************************************" << endl;
cout << "Mostrar arbol: " << endl;
a.preorden();
cout << endl;

// PREGUNTA 3
cout << "****************************************" << endl;
if (a.esExtendido())
cout << "Es Extendido.";
else
cout << "No es Extendido.";
cout << endl;

// PREGUNTA 4 Notacion Infija
cout << "****************************************" << endl;
cout << "Notacion Infija : " << endl;
cout << a.notacion_infija();
cout << endl;

// PREGUNTA 5
cout << "****************************************" << endl;
cout << "Notacion funcional: " << endl;
notacion_funcional (a);
cout << endl;

// PREGUNTA 6
cout << "****************************************" << endl;
cout << "Evaluar arbol: " << evaluar(a);
cout << endl;

////////////////////////////////////////////////////
cout << "Introducir otra cadena? (s/n)? ";
cin >> sig;
cout << endl;

} // Final del while

return 1;
}

/********************************************//********************************************/
/********************************************//********************************************/
Esto es todo, para compilar como supongo q ya sabreis ...
$ g++ main.cpp && ./a.out

Un saludo !

Responder