Arbres et fonctions

Bonjour,

J'ai beaucoup de mal à implémenter les structures de données que je souhaite en java. Je ne sais pas si le problème vient de moi où du langage, mais je me sens beaucoup plus à l'aise dans d'autres langages.

Ma structure de donnée est celle-là (en Caml / F#) :

Code:

---

1 2 3

type 'a ast = | Op of ('a -> 'a -> 'a) * 'a ast * 'a ast | Val of 'a

---

En clair, c'est un arbre binaire où les nœuds sont des fonctions (à 2 arguments) et les feuilles des valeurs. Je souhaite que mon type reste générique, de sorte que les feuilles puissent être des entiers, des flottants, des strings ou autres.

Par la suite, je souhaite pouvoir évaluer l'arbre. Code en ml/F# :

Code:

---

1 2 3

let rec eval = function | Op (f, x, y) -> f (eval x) (eval y) | Val n -> n

---

Et pour tester, j'aimerais pouvoir entrer en arbre en dur, de façon assez claire et lisible. J'avais écrit ça en Caml :

Code:

---

1 2 3 4 5 6 7

let make v1 f v2 = Op (f, v1, v2) and (!) n = Val n   let my_ast = make (make !3 (+) !2) (-) (make !40 (/) !10)

---

Bien sûr, j'ai cherché sur google et lu la faq. J'ai quand même plusieurs questions :

. quelle est la solution la plus simple pour modéliser l'arbre ? De ce que j'ai lu, il faudrait faire une classe abstraite et deux classes qui en héritent.

. a priori, je devrais utiliser une interface pour les fonctions de l'arbre (pour remplacer les pointeurs sur fonction). C'est bien ça ? Et c'est possible de faire ça en mélangeant avec les generics ? (j'avoue que je ne vois pas trop comment faire)

. enfin, je dois vraiment créer un objet pour chaque fonction que je veux ajouter ? Je trouve ça excessivement lourd, surtout quand c'est une simple addition ou une soustraction.

Question subsidiaire : vous pensez que c'est possible de convertir mes 10 lignes de ml en moins de 50 lignes de java ? :?


Par avance, merci de vos réponses.

...
J'avous avoir du mal a comprendre tes exemples.
je n'avais jamais entendu parlé de ce langage.

si tu avais moyen de le rediger autrement peut etre?

Le caml, on a pas entendu parler de ca depuis l'INRIA

Non on peut pas faire mieux que avec ton caml, (ca rappel de lambda calcul).

Il faut pas partir si loin dans la modélisation avec des interfaces, générics, abstract etc... Rien empeche de faire ca après une implémentation de classes concretes.

Ta modélisation est un vieux problèmes pour résoudre des formules du genres (2+4)*6/2 etc, qui est de lordre du design pattern interpretor (à lire mais pas simple à comprendre).

Commence par faire une classe OperationNode qui peut contenir d'autres OperationsNode (une arrayList c'est bien), ou alors deux champs puisque c'est binaire, et pas forcément commutatif. Ensuite tu assignes à chaque noeuds un type (genre +, - ou autre) ou opérateur=true ou false (si un nombre) et une valeur (valeur de l'opérateur +/- etc ou le nombre 23, 141 etc).

Chaque classe comporte une méthode récursive qui renvoi la valeur de l'opération effectuée sur ces fils...

bon courage. Tu peux nous présenter ton code si tu veux.

Je dirais:

Code:

---

1 2 3

Interface Fonction<A> { A f(A v1, A v2); }

---

Si tu veux faire une addition d'entiers :

Code:

---

1 2 3 4 5 6

Fonction<Integer> maFonction = new Fonction<Integer>() { public Integer f(Integer v1, Integer v2) { return v1 + v2; } } int result = maFonction.f(5,3);

---

EDIT: Selon les besoins que tu sembles indiquer (appeler une fonction avec des paramètres comme dans ton make), en java tu ne devrais pas avoir besoin d'une structure d'arbre... Après, tu as peut-être des besoins plus complexes que ton exemple donné...

Citation:

---

Il faut pas partir si loin dans la modélisation avec des interfaces, générics, abstract etc... Rien empeche de faire ca après une implémentation de classes concretes.

---

Oui, d'accord. C'est cette vilaine habitude de vouloir faire des choses propres et extensibles.

Citation:

---

Commence par faire une classe OperationNode qui peut contenir d'autres OperationsNode (une arrayList c'est bien), ou alors deux champs puisque c'est binaire, et pas forcément commutatif. Ensuite tu assignes à chaque noeuds un type (genre +, - ou autre) ou opérateur=true ou false (si un nombre) et une valeur (valeur de l'opérateur +/- etc ou le nombre 23, 141 etc).

---

Oui, c'est pas mal. Mais on perd un peu en sûreté : si le booléen est modifié par mégarde, le programme risque de planter à l'exécution (oui, j'ai cette manie de vouloir que le compilateur vérifie tout ce que je tape). Et on gaspille de la place inutilement (d'accord, on s'en fiche).
Je viens de trouver par hasard ce document (http://denis.monasse.free.fr/denis/a.../javatypes.pdf) qui explique bien la chose et présente une manière plus sûre et plus extensible. C'est en passant, comme je le pensais, par une classe abstraite et deux classes implémentées. Mais c'est vrai que c'est plus de code.

Citation:

---

Selon les besoins que tu sembles indiquer (appeler une fonction avec des paramètres comme dans ton make), en java tu ne devrais pas avoir besoin d'une structure d'arbre... Après, tu as peut-être des besoins plus complexes que ton exemple donné...

---

Le make sert juste à construire mon arbre. Si le but était juste de calculer la valeur, j'aurais directement écrit "5 + 3". :)
Mais oui, je passerai par l'interface que tu donnes pour mettre des fonctions dans mon arbre.

Ce qui est vraiment dommage, c'est que je serai obligé d'écrire une classe pour chaque feuille de mon arbre (si ce sont des fonctions différentes).

Merci pour vos pistes.
Il manque plus que l'aspect générics pour avoir une conversion fidèle des 3 lignes de Caml. :)

Citation:

---

Envoyé par azalara

Ce qui est vraiment dommage, c'est que je serai obligé d'écrire une classe pour chaque feuille de mon arbre (si ce sont des fonctions différentes).

---

Tu peux le faire avec les classes anonymes, pas obligé de faire une classe "nommée" pour chaque chose...

Citation:

---

Envoyé par azalara

Il manque plus que l'aspect générics pour avoir une conversion fidèle des 3 lignes de Caml. :)

---

Les generics sur mon interface ne te conviennent pas?

Si si, mais y'en a aussi besoin dans l'arbre. Et je ne maitrise pas, mais ça devrait aller (ça ressemble un peu aux templates du C++).