Árbol de Expresiones en C

[NericSain]

HOLA A TODOS ESOS BUENOS PROGRAMERS, hoy tengo una super urgencia, estoy construyendo un arbol de expresiones: (a+b) * c, algo parecido a lo anterior, pero ya llegue a un punto de inflexion, pues estoy siguiendo unos pasos que encontre en un libro, pero sigo sin entender como contruir ese arbol, mientras ocupo una pila y vaya guardando los nodos actuales que es en donde ire poniendo los operadores, pero la parte recursiva no la entiendo bien..... ayuda porfa vor

Código (c) [Seleccionar] Expandir


void giveMeExpression(char * input)
{
printf(">>> ");
fflush(stdin);
fgets(input,50,stdin);
}

int haveARigth(ArbolBinario a)
{
return a->der == NULL;
}

int haveALeft(ArbolBinario a)
{
return a->izq == NULL;
}

int isOperator(char input)
{
char operators [] = "+-*/^%";
int i;
for(i = 0 ; i< strlen(operators) ; i++)
{
if (operators[i] == input)
return 1;
}
return 0;
}

void assignASon(ArbolBinario boy, ArbolBinario father)
{
if ( haveALeft(father))///si el padre no tiene izq, se le asigna.
{
/* code */
father->izq = boy;
}
else
{
if ( haveARigth(father))///si el padre no tiene der, se le asigna.
{
/* code */
father->der = boy;
}
}
}

ArbolBinario creatNodeCurrent(Pila *p, int first, ArbolBinario currentNode)
{
ArbolBinario a;
a = creaNodo('\0');
if (first != 0)
assignASon(a,currentNode);
push(p,a);
return a;
}

int itIsParentheses(char  *input, int pos)
{
if( input[pos] == '(' )
return 1;
else
return 0;
}

ArbolBinario createArbol(char * input, Pila *p, int pos, ArbolBinario raiz, int primerParentesis)
{
ArbolBinario currentNode  = NULL;
if(pos > strlen(input) - 1)
{
printf("no entra y se sale\n");
printf("\ncurrentNode en funcion es: %p\n",currentNode );
return raiz;
}
else
{
if (  itIsParentheses(input,pos) == 1 && primerParentesis == 0) // si es 1, entonces no sera el primer parentesis
{
/* code */
raiz = creaNodo('\0');
currentNode = raiz;
push(p,currentNode);
pos++;
primerParentesis = 1;
//currentNode->elemento = input[pos];
//printf("\nnuevo Nodo: %p, %p\n", currentNode, raiz);
printf("Entro al if 1, pos  despues : %d y currentNode es: %p\n", pos,currentNode);
imprimePila(*p);
return  createArbol(input,p,pos, currentNode, primerParentesis);
}
else
{
if( itIsParentheses(input,pos) == 1 )//////////caso 2
{
currentNode = creatNodeCurrent(p, pos,raiz);
pos++;
primerParentesis = 1;
printf("Entro al  2if, pos  despues : %d y currentNode es: %p\n", pos, currentNode);
return  createArbol(input,p,pos, currentNode, primerParentesis);
}
else
{
if ( isOperating(input,pos) ==1)/////////CASO 3
{
currentNode = creatNodeCurrent(p, pos,raiz);
currentNode->elemento = input[pos] ;
pos++;
primerParentesis = 1;
printf("Entro al 3if, pos  despues : %d, con elemento: %c y currentNode: %p\n", pos, currentNode->elemento, currentNode);
imprimePila(*p);
return  createArbol(input,p,pos, currentNode, primerParentesis);
}
else
{
if ( isOperator(input[pos]) == 1 )/////////CASO 4
{
currentNode =  pop(p);
raiz->elemento = input[pos];
pos++;
primerParentesis = 1;
printf("Entro al 4if, pos  despues : %d, con elemento: %c y current node es: %p\n", pos, currentNode->elemento, currentNode);
imprimePila(*p);
return  createArbol(input,p,pos, currentNode, primerParentesis);
}
}
}
}
}
}//////////FIN FUNCION



[Serapis]

Ayer te respondi... era una respuesta larga, y cuando fuí a publicarla, él foro me había deslogado por inactividad... y al volver atrás, curiosamente no se recuperó el mensaje (supongo que porque antes tenía desactivado javascript, y en algún punto intermedio lo activé)... en fin me dió pereza rescribir todo de nuevo.

Hoy simplifico, y veo más necesario indicarte esto:
Si necesitas aprender a realizar árboles, cíñete a eso... y deja en paz (de momento, hasta que lo domines), el ejercicio.
Si en cambio necesitas realizar el ejercició, cíñete a eso y olvida de momento los árboles...
Lo que no va bien es que ni sepas de la herramienta ni sepas del materíal. Así no sabe uno que es lo más urgente responderte, porque ambas cosas a la vez resultará lioso.


Si quieres avanzar por un árbol, usa de ejemplo tu propia familia (que es algo que conoces y entiendes bien), basta con las iniciales... no te preocupes si no es binario, ese es un caso particular de los árboles, conviene primero aprender lo genérico...

Decide y aprende una sola cosa de cada vez, y cuando lo domines regresas a la otra cuestión. Así plantea ahora qué necesitas, qué te urge más aprender...

A veces los libros traen malos ejemplos, ejemplos más o menos complejos donde se da por hecho que el que lo lee (es el pecado capital más frecuente en los libros técnicos, y el pecado mortal, cuando se trata de las matemáticas, parece que solo escriben para otros matemáticos, si no visita wikipedia), ya tiene un conocimiento más o menos sólido de otras materias... en esos casos conviene remplazar el ejemplo, por algo que uno pueda resolver bien (entenderlo al margen de lo que trata de enseñar), es decir un ejemplo, no puede ser el objeto de estudio por sí mismo, por eso el nivel de dificultad debe elegirse bien, si no torpedea al que intenta ilustrarse con la ayuda de un libro.

[NericSain]

Hola NEBIRE, en verdad agradezco tu tiempo para ponerle atención a mis dudas, y lastima wue el código no se haya subid, en fin, te agradezco también el apoyo, las palabras y consejos para mejorar y aprender más, te comento que ya hee, estado estudiando por mi cuenta y creo que voy por buen camino.

[srWhiteSkull]

La parte recursiva en un árbol n-ario va encaminada a la búsqueda de valores en los nodos. Tú puedes hacer un árbol y añadir nodos, algo sencillo, pero el problema es cuando requieres hacer una búsqueda en toda esa red de nodos. Existen diversos métodos para recorrerlos.

https://es.wikipedia.org/wiki/Recorrido_de_%C3%A1rboles

Ejemplo

Código (cpp) [Seleccionar] Expandir

#include <string>
#include <vector>
#include <iostream>

// nodo binario
struct NODO {
   std::string valor;
   NODO * izquierdo;
   NODO * derecho;
};

// funcion recursiva
int buscarValor(NODO *nodo, std::string valor)
{
   if (nodo != NULL) std::cout << "Valor nodo = " << nodo->valor << std::endl;

   if (nodo == NULL) {
       std::cout << "Aqui ya no hay mas nodos!! " << std::endl;
       return 0;
   } else if (nodo->valor != valor) {
       if (buscarValor(nodo->derecho, valor) == 0); // cuando llegamos al final de la rama
       else return buscarValor(nodo->izquierdo, valor);
   } else {
       std::cout << "Encontrado!! " << std::endl;
       return 1;
   }
}

int main(){

   NODO arbol;
   NODO izquierdo, derecho;
   NODO izquierdoIzquierdo, izquierdoDerecho;
   NODO derechoIzquierdo, derechoDerecho;

   izquierdoIzquierdo.valor     = "El nodo mas a la izquierda";
   izquierdoIzquierdo.derecho   = NULL; // Amputamos, o podamos
   izquierdoIzquierdo.izquierdo = NULL;
   izquierdoDerecho.valor     = "El nodo derecho del nodo de la izquierda de la raiz";
   izquierdoDerecho.derecho   = NULL;
   izquierdoDerecho.izquierdo = NULL;

   derechoIzquierdo.valor     = "El nodo izquierdo del nodo de la derecha de la raiz";
   derechoIzquierdo.derecho   = NULL;
   derechoIzquierdo.izquierdo = NULL;
   derechoDerecho.valor     = "El nodo mas a la derecha";
   derechoDerecho.izquierdo = NULL;
   derechoDerecho.derecho   = NULL;

   izquierdo.valor     = "El nodo izquierdo";
   izquierdo.izquierdo = &izquierdoIzquierdo;
   izquierdo.derecho   = &izquierdoDerecho;
   derecho.valor     = "nodo derecho";
   derecho.izquierdo = &derechoIzquierdo;
   derecho.derecho   = &derechoDerecho;

   arbol.valor     = "raiz o principal";
   arbol.izquierdo = &izquierdo;
   arbol.derecho   = &derecho;

   std::cout << "El nodo derecho de la raiz contiene : " << arbol.derecho->valor << std::endl;

   // busqueda recursiva
   buscarValor( &arbol, "El nodo mas a la izquierda");

   system("PAUSE");
   return 0;
}

PD ¿Por qué cojones lo centrará?

[NericSain]

Muchas gracias por la ayuda srWhiteSkull