Discussion :

[Self-Mao]

Bonjour,

J'ai besoin d'aide concernant une fonction lisp.

J'ai deux fonctions :

- add qui ajoute un nombre dans un arbre :

Code :

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

1
2
3
4
5
6
(defun add (c tree)
  (cond
    ((not tree) (list c))
    ((char>= c (car tree)) (list (car tree) (cadr tree) (add c (caddr tree))))
    ;;((list (car tree) (add c (cadr tree)) (caddr tree))) ) )
    ((list (car tree) (add c (cadr tree)) (caddr tree))) ) )

- make-tree qui créer un arbre d'après un fichier :
(le fichier contient un caractère par ligne)

Code :

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

1
2
3
4
5
6
7
(defun make-tree (fich &aux (liste nil))
  (setq charlist (open fich :direction :input :if-does-not-exist :error))
  (loop
    (cond
      ((not (setq ligne (read-line charlist nil nil))) (return)) )
    (setq tree (add (read-from-string ligne) tree)) )
  (close charlist) )

Admettons que mon fichier "lettres.txt" contient ceci :

Code :

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

1
2
3
4
5
6
7
#\r
#\a
#\j
#\b
#\m
#\k
#\p

Alors voici ce que j'obtiens dans l’interprète :

Code :

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

1
2
3
4
5
6
> (setq tree nil)
nil
> (make-tree "texte.txt")
t
> tree
(#\r (#\a NIL (#\j (#\b) (#\m (#\k) (#\p)))) NIL)

J'en viens maintenant à la fonction qui me pose problème.
Cette fonction est sensée remplacer la fonction add et insérer directement des éléments dans la liste avec rplacd et replaca.

- On ne peut commencer avec nil car il n'a pas de cdr. Donc on initalise la liste avec le premier élément.

(setq tree (premier_elm))

- Pour ajouter une branche de droite dans un arbre (#\r) il faut au préalable ajoute un branche de gauche : (#\r nil) sinon le second pointeur cdr n'existe pas encore.

- Ma fonction doit comporter un cond avec 6 cas distincts (a, b, c sont des caractères et x est le caractère à insérer) :

1) on a (a) et x > a : on modifie en (#\a nil (x)) avec deux rplacd
2) on a (a (b...)) et x > a : on modifie en (#\a (#\b...) (x)) avec un rplacd
3) on a (# (b...) (c..)) et x >a : on continue avec la branche (c...)
4) on a (a) et x < a : on modifie en (a (x)) avec un rplacd
5) on a (a nil (b...)) et x < a : on modifie en (a (x) (b...)) avec rplaca
6) on a (a (b...) (c...)) et x < a : on continue avec la branche (b...)

Voilà c'est ici que je coince. Je ne sais pas comment m'y prendre pour monter cette fonction. Si quelqu'un peut m'aiguiller je ne refuserais pas.

Merci d'avance.

[jack-ft]

1) on a (a) et x > a : on modifie en (#\a nil (x)) avec deux rplacd
2) on a (a (b...)) et x > a : on modifie en (#\a (#\b...) (x)) avec un rplacd
3) on a (# (b...) (c..)) et x >a : on continue avec la branche (c...)
4) on a (a) et x < a : on modifie en (a (x)) avec un rplacd
5) on a (a nil (b...)) et x < a : on modifie en (a (x) (b...)) avec rplaca
6) on a (a (b...) (c...)) et x < a : on continue avec la branche (b...)

Voilà c'est ici que je coince.

Bonjour.
Qu'est-ce qui coince?
Qu'as-tu essayé?

[Self-Mao]

Bonjour, merci pour ta réponse tout d'abord !

Voici ce que j'ai :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun insert (tree w)
  (cond
    ((and (not (cdr tree)) (char>= w (car tree)))
      (and (rplacd tree '(nil)) (rplacd (cdr tree) (cons (cons w nil) nil))) )
    ((not (cdr tree))
      (rplacd tree (cons (cons w nil) nil)) )
    ((not (cddr tree))
      (rplacd (cdr tree) (cons (cons w nil) nil)) )
    ((not (cadr tree))
      (rplaca (cdr tree) (cons w nil)) )
    ((char>= w (car tree))
      (insert (caddr tree) w) )
    ((insert (cadr tree) w)) ) )

Et voici ce qui coince :

Code :

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

1
2
3
4
5
6
7
8
9
10
> (setq arbre '("k"))
("k")
> (insert arbre "m")
=> ("k" NIL ("m"))
 
> (insert arbre "a")
=> ("k" ("a") ("m"))
 
> (insert arbre "n")
=> ("k" ("a") ("n"))

Je pense que le soucis vient de l'action a effectué dans la première clause de la condition.

Code :

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

(and (rplacd tree '(nil)) (rplacd (cdr tree) (cons (cons w nil) nil)))

Car avec la trace de la fonction je m’aperçois que l'arbre est modifié ainsi :

Code :

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

1
2
3
=> ("k" ("a") ("m"))
=> ("k" ("a") ("m" nil))
=> ("k" ("a") ("n"))

Il y a une erreur quelque part c'est sûr mais je ne sais pas où malheureusement.

!!!!! EDIT !!!!!

Bon apparemment j'ai résolu le problème en modifiant une ligne dans la fonction :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun insert (w tree)
  (cond
    ((and (not (cdr tree)) (char>= w (car tree)))
      (rplacd tree (list nil (list w))) )
    ((not (cdr tree))
      (rplacd tree (cons (list w) nil)) )
    ((not (cddr tree))
      (rplacd (cdr tree) (cons (list w) nil)) )
    ((not (cadr tree))
      (rplaca (cdr tree) (cons w nil)) )
    ((char>= w (car tree))
      (insert w (caddr tree)) )
    ((insert w (cadr tree))) ) )

Je ne comprend pas pourquoi la solution avec les deux rplacd ne fonctionne pas. Elle donne des résultats vraiment étranges. Mais cette nouvelle fonction à l'air de fonctionner parfaitement.

[jack-ft]

Pourquoi si compliqué?

Essaie plutôt de reprendre la structure de la fonction 'add' en supprimant les 'list' (sauf le premier) et faisant systématiquement des rplaca (attention toutefois aux valeurs retournées!)

La fonction devrait faire juste 2 ou 3 lignes de plus que 'add' (à cause des valeurs retournées (progn implicite dans les clauses de cond)).

[jack-ft]

Voici une solution possible calquée sur 'add', courte, mais qui fait beaucoup d'écritures:

Code lisp :

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

1
2
3
4
5
6
7
8
9
(defun insert (c tree)
  (cond
   ((not tree) (list c))
   ((char>= c (car tree))
    (rplaca (caddr tree) (insert c (caddr tree)))
    tree)
   (t
    (rplaca (cadr tree) (insert c (cadr tree)))
    tree)))

et une solution un peu plus longue (qui duplique le code '(list c)'), qui fait le double de tests, mais qui fait juste les écritures nécessaires:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(defun insert (c tree)
  (cond
   ((not tree) (list c))
   ((char>= c (car tree))
    (if (caddr tree)
        (insert c (caddr tree))
      (rplaca (cddr tree) (list c)) ))
   (t
    (if (cadr tree)
        (insert c (cadr tree))
      (rplaca (cdr tree) (list c)) ))))

et une solution encore plus rapide:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun insert (c tree)
  (if tree
      (insert-aux c tree))
  (list c))
 
(defun insert_aux (c tree)
  (if (char>= c (car tree))
      (if (caddr tree)
          (insert_aux c (caddr tree))
        (rplaca (cddr tree) (list c)) )
    (if (cadr tree)
        (insert_aux c (cadr tree))
      (rplaca (cdr tree) (list c)) )))

[Self-Mao]

Merci pour ta réponse.

En effet j'avais tenté quelque chose du genre avec des if, peut-être pas aussi rapide mais c'est pour un devoir et je suis forcé d'utiliser des cond mais en définissant les clauses je suis parvenu à un bon compromis, avec cond et pas de if.

Merci infiniment de ton aide !!

[simnitch]

Aucune de tes fonctions ne marche chez moi jack-ft...

[Trap D]

Genre déterrage c'est pas mal !
En plus quelques explications sur les erreurs/problèmes rencontrés serait utile.

[simnitch]

Genre déterrer un vieux sujet c'est mal? On parle d'arbres là en plus, donc c'est dans le vif du sujet, ahah.
Le problème c'est que ça ne marche pas du tout, même message d'erreur pour les trois fonctions : rplaca : nil n'est pas une paire.
Ca marche seulement pour rentrer un caractère dans un arbre vide.
Voilà c'est tout...

[simnitch]

Du coup personne n'a une solution qui marche?
Merci d'avance