salut,
j'ai un probleme pour évaluer une expression dans une arbre,
j'ai bien compris que si mon noeud est un signe, je devais l'appliquer aux deux opérandes droit et gauche, par contre si les fils sont aussi des signes, je devais appeler récursiviement la fonction (?).
Le principe de récursivité est encore flou chez moi...
voila ce que j'ai fait : http://pastebin.com/Xf5y40Cz

merci j'espere que vous pourrez m'aider a comprendre mieux.

Ton idée n'est pas fausse mais tu prends "un niveau d'avance" en regardant les étiquettes de tes fils. Tu dois regarder uniquement l'étiquette du noeud courant.

Si mon étiquette est un entier, je renvoie cet entier
Si mon étiquette est un signe, je me rappelle récursivement sur mes deux sous-arbres et j'effectue l'opération correspondante

Merci de ta réponse, mais je ne comprends pas pourquoi il faut renvoyer l'entier quand on en voit un, et aussi comment le résultat peut etre sauvegardé vu qu'a chaque appel res se remet à 0 ?
merci.

En fait tu penses de manière impérative et non récursive. Il ne faut pas essayer de comprendre ce que fait ton programme de manière globale sur toute la structure d'arbre. Tu n'es pas en train d'effectuer un parcours de l'arbre.

En fait, le principe, c'est que tu t'autorises à supposer que tu disposes déjà de la fonction eval() qui fonctionne et qui fait ce que tu veux, c'est à dire qu'elle évalue un arbre. La seule restriction, c'est que tu dois la rappeler sur une entrée plus petite que ton entrée initiale, c'est à dire sur des sous-arbres.

Disons que la racine de ton arbre soit un signe, par exemple "+".
Tu dois donc faire la somme de la valeur du sous-arbre de gauche, avec la valeur du sous-arbre de droite. Comme tu as le droit de rappeler ta fonction sur les sous-arbres, eh bien c'est très simple :
- Tu appelles eval() sur le sous-arbre gauche pour avoir sa valeur
- Tu appelles eval() sur le sous-arbre droit pour avoir sa valeur
- Tu renvoies la somme des deux valeurs obtenues.

Il faut aussi traiter le cas de base, c'est à dire les feuilles de l'arbre, qui correspondent en fait aux entiers.
Si ton arbre est réduit à un seul noeud qui est étiqueté par un entier, évaluer cet arbre ça revient à renvoyer l'entier.

Ah oui j'ai oublié ta question, "comment le résultat peut être sauvegardé si à chaque fois res est remis à zéro".

En fait, à chaque fois que tu rappelles ta fonction, elle s'exécute dans un nouvel environnement, c'est-à-dire que des cases mémoires sont réallouées pour toutes les variables locales (comme "res"). En d'autres termes, à chaque appel récursif, la variable "res" dont tu te sers pour faire des calculs sera différente de celle des appels précédents.

Au premier appel de ta fonction eval(), il se crée une première variable "res", que je vais appeler res_1. Elle est initialisée à 0.
Puis tu rappelles récursivement ta fonction sur le premier sous arbre. Lorsque cet appel récursif est exécuté, l'instruction "int res = 0" va créer une nouvelle variable "res", que je vais appeler res_2. Il s'agit d'une autre case mémoire qui n'a rien à voir avec res_1. Ta fonction fait éventuellement plein d'autres appels récursifs en descendant dans le sous-arbre gauche, créant ainsi res_3, res_4, ..., res_42.
Au bout d'un moment, l'une de ces valeurs finit par être renvoyée : on remonte d'un cran, et la valeur res_42 qui a été calculée peut être utilisée pour mettre à jour res_41, qui sera à son tour renvoyée et utilisée par l'appel précédent, etc. L'espace mémoire utilisé par chacune de ces cases est libéré au fur et à mesure que les appels de fonctions successifs se terminent.

Après, comment tout ça est géré exactement dans la pile, c'est un peu plus compliqué. Mais de toute façon pour écrire des programmes récursifs, c'est inutile de réfléchir à ce qui se passe réellement dans la mémoire. Il faut abstraire tout ça et juste se demander "en supposant que ma fonction marche sur les sous-arbres, comment je fais pour calculer ce qu'il faut ?". Si tu essayes de tout dérouler dans ta tête tu vas faire des spaghetti dans ton cerveau

Waa merci de prendre le temps de m'aider c'est tres sympa
Je crois en plus que as cerné mon probleme , j'ai bcp de mal a visualiser la récursion et finalement c'est en fait pas la peine d'apres ce que j'ai compris.
Voila ce que j'ai fait : http://pastebin.com/z0gFfEwG
je crois que ca s'approche du résultat .
Mais en fait je vois toujours pas a quel moment faire le calcul , car si par exemple j'ai plusieurs noeud étiqueté avec un signe
qui s'enchaine, comment faire l'opération?

bon je suis sur que ma question est bizarre mais je crois que tu as raison, j'ai deja des spaguhetti dans ma tete

j'espere finir par comprendre completement !
merci.

C'est pas mal, en fait ce que je te proposait moi c'était encore plus simple, ça donnerait ça :
http://pastebin.com/4dXP3fVZ
(d'ailleurs c'est un détail mais même si j'ai jamais fait de java j'imagine que tu dois avoir la possibilité de mettre "else" quand même, au lieu de ton deuxième if )

En fait là, je suppose deux choses :
Que l'arbre est bien formé, c'est à dire qu'il a comme noeuds internes des signes + - * /, et comme feuilles des entiers.
Que tous les opérateurs sont binaires, c'est à dire que tu peux faire "x - y" (un signe - avec x et y comme fils) mais pas - x (un signe - avec un seul fils qui est x).
En particulier, je supposais donc qu'on ne puisse pas avoir "null" comme fils d'un noeud + - * /.

C'est un bon début. Après, si tu veux pouvoir faire un truc plus général, il va falloir avoir la possibilité de renvoyer "cet arbre ne peut pas être évalué", par exemple si tu as une expression du type 3 +*/-- 6, elle n'a pas de sens...
En fait, les erreurs surviennent :
- si il y a un * ou un / avec moins de deux fils
- si il y a un + ou un - avec aucun fils
- si tu appelles ta fonction sur l'arbre "null"

Je te laisse essayer de coder ça

Ok je vois. Effectivement j'ai fait auparavant une fonction qui vérifie qu'un arbre est bien formé.
Par contre j'ai un arbre témoin un peu spécial, voici son écriture prefixée : - * + 1 2 - / 6 3 4

Ca fait que des le début la racine n'a qu'un noeud (on suppose que c'est le noeud droit et le noeud gauche est à null), donc g = this.gauche.eval(); me renverra une erreur.
Est ce que ca veut dire qu'on ne peut pas calculer l'arbre ou qu'il faut juste rajouter quelque chose ?

Oui donc là c'est le deuxième point dont je parlais dans le message précédent. Il faut que tu autorises le signe - à n'avoir qu'un seul fils (et le signe + aussi, pourquoi pas. Ca fait un peu bizarre de pouvoir évalier --++-4, mais en même temps on a envie de pouvoir évaluer +8 je pense)

Du coup, si tu supposes que l'unique fils est toujours placé à droite, ça simplifie légèrement les choses.
L'appel à this.droite.eval() ne pose pas problème : il existe toujours.
Reste à faire une disjonction de cas suivant que le fils gauche soit NULL ou pas.

Si this.gauche == NULL, dans le cas de + et - tu dois renvoyer un résultat, mais dans le cas de * et / tu dois renvoyer une erreur
Si this.gauche != NULL, tu fais comme avant

okk donc voila ce que j'ai maintenant : http://pastebin.com/1NBGvgQf

je vois encore quelques problemes ; dès le debut la condition sera vérifiée donc finalement le programme ne va rien faire , aussi je dois convertir mes string en double avec doubleValue(), et je sais pas où le faire sans que ca bug..

Non là c'est pas bon, dans le cas où l'arbre gauche est NULL tu dois quand même évaluer l'arbre droit pour qu'il se passe des choses, pas renvoyer le résultat tout de suite

De plus, le bloc suivant est mal placé :
if(this.etiquette.equals("-")) res = g - d;
if(this.etiquette.equals("+")) res = g + d;
if(this.etiquette.equals("*")) res = g * d;
if(this.etiquette.equals("/")) res = g / d;
Il devrait être dans le else, vu qu'il correspond au cas où g et d sont définis

Oui c'est vrai j'ai oublié de vérifier le droit meme quand le gauche est null (la fatigue )

voila ce que j'ai : http://pastebin.com/9K32Enmq
probleme : aucun affichage (plus d'erreur au moins c est deja ca)
Ca m'a l'air bien pourtant là

Omg ca marche !! ( oublie mon dernier message j'avais juste oublié de mettre un println pour afficher le résultat) .

voila le résultat final : http://pastebin.com/zJYGC4YX (apres avoir ajouté la condition avec le return res; )

merci beaucoup Lowenheim de m'avoir accordé du temps,
je suis pas encore un pro de la récursion mais j'ai bien mieux compris. merci

Deux remarques :
- Tu peux factoriser la ligne "d = this.droit.eval();" en la mettant juste avant ton if.
- Tu ne fais pas ce qu'il faut quand l'arbre gauche est NULL, tu renvoies res sans avoir changé sa valeur à aucun moment, autrement dit tu renvoies zéro !
Souviens toi que la variable "res" des appels récursifs n'est PAS la même que ta variable "res" courante ! Il faut que tu utilises la valeur renvoyée par la fonction eval(), c'est à dire res.
http://pastebin.com/cJz3FEgV
http://pastebin.com/zLdz6vS7

Oula je suis fatigué je sais pas pourquoi y'a deux liens le contenu a l'air identique, et je voulais dire "Voilà à quoi ça doit ressembler je t'ai fait (presque) tout le travail mais essaie de le faire sans regarder ma solution et juste en suivant mes indications"

voila c'est ca normalement : http://pastebin.com/hvTqy9qt
mais ici le "chemin" n'est pas le meme qu'avant, enfin il va aller a droite avant d'aller a gauche, c'est pas important non?
Aussi j'ai une question sur cette ligne : if(estNombre(this.etiquette)) {
return new Double(this.etiquette).doubleValue();
}

qu'est ce qu'elle fait exactement ? j'arrive pas a voir ou on l'utilise dans la récursion( tu peux me répondre demain si tu es trop fatigué )

Aller à droite en premier n'est pas important non, tu peux laisser comme avant si tu préfères ça revient vraiment au même ça fait juste une ligne de code de plus

Cette ligne sert à évaluer des arbres qui sont réduits à un seul noeud étiqueté par un entier.
L'expression "3" te donne un arbre qui a un noeud "3" et deux fils "NULL", et quand tu l'évalues, tu renvoies 3.

Si tu veut évaluer l'arbre 2 + 3 :
- tu commences à la racine qui est étiquetée par "+", du coup tu commences par évaluer le sous-arbre droit
- ce sous arbre n'a qu'un noeud étiqueté par "3" : l'algo renvoie la valeur 3
- en remontant à l'arbre principal, tu auras donc d = 3, puis tu vas rappeler eval() sur le sous-arbre gauche
- c'est aussi un arbre à un seul noeud "2" : il renvoie 2
- du coup, en remontant, g = 2
- il renvoie res = 2 + 3

ok je pense que j'ai compris, ben merci pour ton aide en tout cas désolé de t'avoir soulé avec mes questions