[C] Factorisation d'arbre en C Fermé

Question

Bonjour !!
J'aurait besoin de conseil en vue de créer une fonction C pour factoriser un arbre. voici le début de mon programme. Il prend en paramètre un ensemble de clause ( exemple: x|y|nz,nx|ny,ny|nz,z ) , ensuite il tranforme l'expression en un arbre. (seul les 3 variables x, y, z sont possible , ou s'écrit| et non x s'écrit nx ) puis il simplifie l'arbre en ramplacant un noeud avec un 0 en filsgauche par son filsdroit .
Je voudrait maintenant le factoriser comme suit :

[URL=http://img174.exs.cx/my.php?loc=img174&image=sanstitre2ay.jpg][IMG]http://img174.exs.cx/img174/9806/sanstitre2ay.th.jpg[/IMG][/URL]

Un peu d'aide, une idée, un algorithme de factorisation serait bienvenue.
Merci d'avance.
Guillaume Coutelle

Coutelle Guillaume · Answer

j'ai oublié de mettre le code du début de notre programme !! lol
Le voici:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct cellule{
char var[2];
struct cellule *filsg;
struct cellule *filsd;
}type_cellule;

typedef struct cellule *arbre;

arbre cc(char nom[2], type_cellule *g, type_cellule *d )
{
type_cellule *cellule1;
cellule1 = (type_cellule*)malloc(sizeof(type_cellule));
strcpy(cellule1->var,nom);
cellule1->filsg = g;
cellule1->filsd = d;
return cellule1;
}

void affiche(arbre A){

printf(A->var);
if(A->filsg != NULL) affiche(A->filsg);
if(A->filsd != NULL) affiche(A->filsd);
}

arbre simplif (arbre A)
{
printf( "\n on est au tour A->var = %s\n", A->var );
arbre B;
if ( (A->filsg==NULL) && (A->filsd==NULL) ) {
printf( "cas ou a->g & a->d sont nuls\n" );
return A;
}
if ( (A->filsg->filsg!=NULL) && (A->filsg->filsd!=NULL) ) {
printf( "cas ou a-g-g & a-g-d non nuls\n Voici a-g-g-var : %s\n", A->filsg->filsg->var );
if ( strcmp( A->filsg->filsg->var, "0" ) == 0 ) {
printf( "cas ou a-g-g-var = 0\n" );
B = A->filsg->filsd;
free( A->filsg->filsg );
A->filsg = B;
printf( "changement du a-g-var : %s\n", A->filsg );
}
if ( A->filsd != NULL )
simplif( A->filsd );
if ( A->filsg != NULL )
simplif( A->filsg );
}
if ( (A->filsd->filsg!=NULL) && (A->filsd->filsd!=NULL) ) {
printf( "cas ou a-d-g & a-d-d non nuls\n Voici a-d-g-var : %s\n", A->filsd->filsg->var );
if ( strcmp( A->filsd->filsg->var, "0" ) == 0 ) {
printf( "cas ou a-d-g-var = 0\n" );
B = A->filsd->filsd;
free( A->filsd->filsg );
A->filsd = B;
printf( "changement du a-d-var : %s\n", A->filsd );
}
if ( A->filsd != NULL )
simplif( A->filsd );
if ( A->filsg != NULL )
simplif( A->filsg );
}
return A;
}

arbre simplifarbre(arbre A)
{
int i=8;
while(i>0)
{
printf("tour num %i\n",i);
A=simplif(A);
affiche(A);
printf("\n");
i--;
}
return A;
}
arbre ajoutc( char *c, arbre arbree){

struct cellule *ptr = arbree;
int n,i,k=0;
n = strlen(c);
for(i=0;i<n;i++){
if( c[i]!='|'||c[i]!='\0' ){
if(c[i]=='n' && c[i+1]=='x')
{ptr = ptr->filsd->filsg;
k=1;}
else if(c[i]=='x')
{ptr = ptr->filsg->filsd;
k=1;}
}
if(k==1)i=n;}
if (k==0) ptr = ptr->filsd->filsd;
k=0;
for(i=0;i<n;i++){
if( c[i]!='|'||c[i]!='\0' ){
if(c[i]=='n' && c[i+1]=='y')
{ptr = ptr->filsd->filsg;
k=1;}
else if(c[i]=='y')
{ptr = ptr->filsg->filsd;
k=1;}
}
if(k==1)i=n;}
if(k==0) ptr = ptr->filsd->filsd;
k=0;
for(i=0;i<n;i++){
if( c[i]!='|'||c[i]!='\0' ){
if(c[i]=='n' && c[i+1]=='z')
{ptr = ptr->filsd->filsg;
k=1;}
else if(c[i]=='z')
{ptr = ptr->filsg->filsd;
k=1;}
}
if(k==1)i=n;}
if(k==0) ptr = ptr->filsd->filsd;
strcpy(ptr->var,"1") ;
return arbree;
}

int main (int argc, char *argv[])
{
int i=0,j=0,n=0,nbformule=1;
arbre arbre1;
printf("%s \n",argv[1]);
while(argv[1][i]!='\0')
{if(argv[1][i]==',')nbformule++;
i++;}
printf("%i\n", nbformule);
char formule[nbformule][9];
i=0;
while(argv[1][i]!='\0')
{if(argv[1][i]==',') {
formule[n][j]='\0';
n++;
j=0;}
else { formule[n][j]=argv[1][i];
j++;}
i++;}
formule[n][j]='\0';

arbre1 = cc("x",cc("nx",cc("0",NULL,NULL)
,cc("y",cc("ny",cc("0",NULL,NULL),cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL))))
,cc("ny",cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))
,cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL))))))
,cc("nx",cc("y",cc("ny",cc("0",NULL,NULL),cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL))))
,cc("ny",cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))
,cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))))
,cc("y",cc("ny",cc("0",NULL,NULL),cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL))))
,cc("ny",cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))
,cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))))));

affiche(arbre1);
printf("\n");
for(i=0;i<nbformule;i++)
{printf("%s\n",formule[i]);
arbre1=ajoutc(formule[i],arbre1);
}
printf("\n");
affiche(arbre1);
printf("\n");
arbre1=simplifarbre(arbre1);
affiche(arbre1);

j = 0;
while( j<10 )
printf( "Hi\b\b" );
return 0;

}

kij · Answer

Ah ah ah , l'analyse des expression, quelle belle merde à faire !

Si tu veux un algo déjà fait je peux te filer le miens (eh oui g du en faire un aussi cette année), mais c'est en java, si tu connait un peu le langage, tu pourra reprendre le principe.
Le probleme, c'est que je ne pourrait te l'envoyer que la semaine prochaine (g oublié mon dur ché ma cops)

Voilà si t'en a toujour besoin redi le moi

++

Guillaume Coutelle · Answer

Yep , yep, yep !! Je connais le language Java et oui  je suis interessé par ton algo, pour la semaine prochaine y pas de problème.M'oublie pas, merci d'avance.Guillaume Coutelle

Guillaume Coutelle · Answer

Bah voilà j'attend ton algo avec impatience !!!:-)god_is_a_dj

[C] Factorisation d'arbre en C

4 réponses

Discussions similaires