algo d'arbre binaire

Version imprimable

27/09/2006, 17h07
sad-evil

algo d'arbre binaire

salut a tous!!,je cherche un algo pour l'acquisition d'une fonction booléenne et sa transformation en un arbre binaire(variables sur les feuilles et operateurs sur les noeuds)
merci d'avance:roll:
27/09/2006, 18h58
millie

Citation:

l'acquisition d'une fonction booléenne

Tu parles de fonction booléenne ou tu veux parler d'une expression logique ?
27/09/2006, 20h13
EA2Ien en perdition

bonjour,
c'est une fonction booléenne avec des opérateurs "+" "." et "/" pour les compléments. par exemple une fonction f(a,b,c)=/(a.(b+c))
27/09/2006, 20h23
millie

ok, dans ce cas c'est une expression logique, et pas purement une fonction booléenne, ce qui rend la chose plus facile.

Souhaites tu construire l'arbre pour l'évaluer ensuite ? Il y a des méthodes performantes dans des cours de Compilation utilisant des piles pour réaliser cela.

suffit d'une fonction recursive... la difficulté est de parser correctement la formule !

en gros, ca donne un truc du genre :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 
arbre A
 
Construct(chaine C) retourne un arbre
  si C est de la forme /(uneChaine)
    ajouter a A un noeud avec operateur / et une branche vers Construct(uneChaine)
 
   si C est de la forme (uneChaine + uneAutreChaine)
     ajouter a A un noeud avec operateur + et 2 branche vers Construct(uneChaine) et Construct(uneAutreChaine)
 
//pareil pour l'operateur .
 
  si C est une variable, la renvoyer

27/09/2006, 20h27
EA2Ien en perdition

oui exactement. parce que ensuite il va servir à un autre sous programme qui lui va le simplifier on va dire, en une somme de produit qui va etre retranscrite encore une fois en un arbre. et cette somme de produit sera utiliser et donc doit etre facilement manipulable, par un autre programme.
27/09/2006, 20h58
EA2Ien en perdition

donc voilà seulement, de l'ADA j'en ai fait peu, et avec un prof passe moi l'expression mais un prf de me***, donc je sèche pas mal sur l'algo et le programme d'ou le coup de main que je demande.
28/09/2006, 23h06
sad-evil

j'attend tjrs une reponse + satisfaisante :?
29/09/2006, 09h14
Nemerle

Citation:

Envoyé par sad-evil

j'attend tjrs une reponse + satisfaisante :?

:? bein tu vas attendre longtemps avec ce genre de réaction
29/09/2006, 10h45
jobherzt

Citation:

Envoyé par Nemerle

:? bein tu vas attendre longtemps avec ce genre de réaction

tu m'etonnes :mouarf:

je t'ai donné un algo, bancal peut etre, improvisé surement, mais je ne suis pas la pour faire ton boulot a ta place...
09/10/2006, 16h30
EA2Ien en perdition

bonsoir, voilà, vous m'avez bien conseillé pour mon problème, mais je tourne toujours en rond, je tatonne sans avancer dans mon projet pourriez-vous s'il vous plaît m'indiquer des sites internet ou il y aurait un cours sur la construction et surtout transformation de fonction logique en arbre binaire. merci d'avance;)
09/10/2006, 16h36
jobherzt

je t'ai donné l'algorithme dans mon premier post, qu'est ce qui ne te va pas ?
09/10/2006, 16h44
EA2Ien en perdition

oui tu m'a donné un algorithme, le problème c'est que je suis pas trés doué en ada, mais bon je suis encore que à l'algorithme dieu merci... ce qui ne me va pas c que je sais pas par ou commencé avec mon projet jessaye des méthode qui ne me mène à rien ,j'ai un prof trop nul qui se fou de nous parce que on compren pas, donc il ne nous aide pas.
voilà donc pour ton algo, au début j'ai (une chaine) d'accord, avec des carctères, des opérateurs etc... déjà, ais-je besoins d'analyser la fonction que je rentre avant d'en fair un arbre ou est-ce possible d'attaquer la construction directement?