Discussion :

[krolle666]

Voilà j'ai besoin de vous pour créer une fonction, cela fait 2 jours que je comprend vraiment pas comment je peux faire ça:

Écrire la définition complète de la fonction expr->agb qui, pour une ExprBoolPrefixe E donnée, représentant une expression bien formée, rend l’ArbreGenBool représentant cette liste E.

Par exemple :

(expr->agb ’v) rend l’arbre représenté par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 (ag-noeud ’v (list))

(expr->agb ’(et (ou v f) (non f))) rend l’arbre représenté par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
(ag-noeud ’et
          (list (ag-noeud ’ou
                          (list (ag-noeud ’v (list))
                                (ag-noeud ’f (list))))
                (ag-noeud ’non
                          (list (ag-noeud ’f (list))))))

(expr->agb ’(non (et (ou v f) (et v v)))) rend l’arbre représenté par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
(ag-noeud ’non
          (list (ag-noeud ’et
                          (list (ag-noeud ’ou
                                         (list (ag-noeud ’v (list))
                                               (ag-noeud ’f (list))))
                     (ag-noeud ’et
                               (list (ag-noeud ’v (list))
                               (ag-noeud ’v (list))))))))

(expr->agb ’(non (non v))) rend l’arbre représenté par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
(ag-noeud ’non
          (list (ag-noeud ’non
                          (list (ag-noeud ’v (list))))))

Le principe c'est que je dois créer un évaluateur et je dois pouvoir etudier 4 formules qui sont:

v
(et (ou v f) (non f))
(non (et (ou v f) (et v v)))
(non (non v))

mais pour ça faut pouvoir les transforrmer en arbre.

Si vous pouviez m'aider, me mettre sur la piste ou n'importe quoi d'autre je suis preneur.

Merci d'avance,

[jack-ft]

C'est pourtant très simple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Pour calculer le expr->agb d un truc
si le truc n'est pas une liste
alors (d après le premier exemple)
  retourner un arbre avec truc et une liste vide
sinon
  retourner un arbre avec (car truc) et la liste (cdr truc)

Pour calculer un arbre avec un noeud truc et une liste feuilles
  créer une liste avec les 3 éléments:
    le symbole "sg-noeud"
    le truc quoté
    une liste contenant:
      le symbole "list"
      l'application de expr->agb à chacune des feuilles

Après y a plus qu'à coder!

Élémentaire... (ie. laissé en exercice au lecteur)

Rq: le programme lisp doit avoir à peu de choses près le même nombre de lignes que l'algorithme fourni

[krolle666]

Merci pour la réponse, désolé pour le retard j'étais pas mal occupé.

Donc pour te répondre, je suis pas sur d'avoir compris le principe:

je te montre ce que j'ai fait pour l'instant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
(define (expr->agb E)
  (if (list? E)
      (ag-noeud (car E) (list))
        (ag-noeud (car E)
                  (list (ag-noeud (cdr E) (list))))))

Donc ça me crée un arbre avec le premier terme de l'exemple, par je ne sais pas ou appliquer la recursivité, il faut que je remette un "expr->agb" mais je vois vraiment pas comment ... avec un "let" peut être ?

Merci d'avance

[jack-ft]

Donc pour te répondre, je suis pas sur d'avoir compris le principe:

je te montre ce que j'ai fait pour l'instant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
(define (expr->agb E)
  (if (list? E)
      (ag-noeud (car E) (list))
        (ag-noeud (car E)
                  (list (ag-noeud (cdr E) (list))))))

Les 2 premières lignes sont bonnes. C'est déjà ça!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(define (expr->agb E)
  (if (list? E)

En ce qui concerne la ligne suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

      (ag-noeud (car E) (list))

tu dis:

Donc ça me crée un arbre

Je n'en suis pas si sûr!
Ce qui est certain, c'est que tu appelles la fonction "ag-noeud".
Est-ce que cette fonction existe?
Est-ce qu'elle crée un arbre?

Dans ma proposition d'algorithme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  retourner un arbre avec truc et une liste vide

il fallait entendre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  appeler la fonction 'calculer un arbre' décrite ci-dessous avec truc et une liste vide

Ceci devrait aussi répondre à la question suivante:

avec le premier terme de l'exemple, par je ne sais pas ou appliquer la recursivité, il faut que je remette un "expr->agb" mais je vois vraiment pas comment ... avec un "let" peut être ?

Relis l'algorithme à la lueur de ces explications.

[jack-ft]

Je viens de relire le post originel et j'entrevois quelque chose que je n'avais pas vu/compris.

(expr->agb ’(et (ou v f) (non f))) rend l’arbre représenté par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
(ag-noeud ’et
          (list (ag-noeud ’ou
                          (list (ag-noeud ’v (list))
                                (ag-noeud ’f (list))))
                (ag-noeud ’non
                          (list (ag-noeud ’f (list))))))

Qu'entends-tu par "l’arbre représenté par"?

Je vois 2 réponses possibles:
- l'arbre retourné par l'appel de l'expression (ag-noeud ’et ...) où ag-noeud est une fonction existante (de construction d'arbre, probablement) ou à définir
- la liste (ag-noeud ’et (list (ag-noeud ’ou ...))) c'est-à-dire une liste contenant le symbole ag-noeud puis le symbole quoté 'et puis une liste commençant par le symbole 'list etc.

J'avais initialement pensé à la 2ème option et fourni l'algo en conséquence, mais, si la fonction ag-noeud existe, alors ce serait plutôt la 1ère option et mon algo est à revoir...

[krolle666]

La fonction ag-noeud existe bel et bien.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
(ag-noeud ’et
          (list (ag-noeud ’ou
                          (list (ag-noeud ’v (list))
                                (ag-noeud ’f (list))))
                (ag-noeud ’non
                          (list (ag-noeud ’f (list))))))

Construit l'arbre:

......et
..../....\
..ou....non
./...\......\
v.....f......f

C'est ce qui me bloque en l'occurrence, il faut que lrsque je tappe

(expr->agb ’(et (ou v f) (non f)))

cela me rende un arbre identique à si j'avais tappé ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
(ag-noeud ’et
          (list (ag-noeud ’ou
                          (list (ag-noeud ’v (list))
                                (ag-noeud ’f (list))))
                (ag-noeud ’non
                          (list (ag-noeud ’f (list))))))

et je n'arrive vraiment pas à définir ma fonction (expr->agb) qui me construit un arbre de façon récursive.

[jack-ft]

La fonction ag-noeud existe bel et bien.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
(ag-noeud ’et
          (list (ag-noeud ’ou
                          (list (ag-noeud ’v (list))
                                (ag-noeud ’f (list))))
                (ag-noeud ’non
                          (list (ag-noeud ’f (list))))))

Construit l'arbre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
......et
..../....\
..ou....non
./...\......\
v.....f......f

C'est ce qui me bloque en l'occurrence, il faut que lrsque je tappe

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(expr->agb ’(et (ou v f) (non f)))

cela me rende un arbre identique à si j'avais tappé ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
(ag-noeud ’et
          (list (ag-noeud ’ou
                          (list (ag-noeud ’v (list))
                                (ag-noeud ’f (list))))
                (ag-noeud ’non
                          (list (ag-noeud ’f (list))))))

et je n'arrive vraiment pas à définir ma fonction (expr->agb) qui me construit un arbre de façon récursive.

Je vois.
Du coup, l'algo est encore plus simple que ma première proposition!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Pour calculer le expr->agb d un truc
si le truc n'est pas une liste
alors (d après le premier exemple)
  appeler ag-noeud avec truc et une liste vide
sinon
  appeler ag-noeud avec (car truc) et l'application de expr->agb à chacune des feuilles

Et, bonne nouvelle, les 4 premières lignes de ton code sont presque bonnes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
(define (expr->agb E)
  (if (list? E)
      (ag-noeud (car E) (list))
      (ag-noeud (car E)
                  (list (ag-noeud (cdr E) (list))))))

La 3ème n'est pas conforme: si E n'est pas une liste, tu ne peux pas en prendre le car!
Reste la 5ème et dernière...
jette un coup d'oeil à la fonction map

[jack-ft]

D'où la solution:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
(define (expr->agb E)
  (if (not (list? E))
      (ag-noeud E (list))
      (ag-noeud (car E) (map 'expr->agb (cdr E)))))