Discussion :

[johhry]

Bonjour à tous,

Je ne sais pas si je poste dans la bonne catégorie de forum (car je n'ai pas trouvé mieux) mais voici mon problème :

Je suis en train de faire un exercice à propos des arbres binaires. L'idée est d'après une classe Node (qui représente un noeud de l'arbre), écrire une fonction "serializable(node)" qui transforme cet arbre en chaîne de caractères.
J'ai déjà codé cette fonction et voici la manière dont j'ai formaté cette chaine :

Code ruby :

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

1
2
3
4
5
root(left(left.left($,$),$),right($,$))
 
ou encore
 
1(7($,$),3($,3($,$)))

avec root(left,right) qui représente un noeud ("root", "left" et "right" peuvent être n'importe quelle chaine de caractères) et "$" l'absence de noeud fils.

Maintenant il m'est demandé d'écrire la fonction "deserialize(str)" qui effectue l'opération inverse.
Il me faut donc un moyen de parser la chaine et d'extraire les composantes (valeur du noeud, gauche et droite) du noeud récursivement.

Je code en Ruby donc je peux utiliser facilement la fonction "String#split" qui prends en argument une expression régulière.
J'aimerais donc avoir :

Code ruby :

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

1
2
3
4
5
6
7
8
9
10
root(left(left.left($,$),$),right($,$))
left(left.left($,$),$)    right($,$)
left.left($,$)   $       $    $
$    $
 
ou encore
 
1(7($,$),3($,3($,$)))
7($,$)    3($,3($,$)) 
$  $        $    3($,$)

et ainsi reconstruire l'arbre binaire.
Ma question : à quoi doit ressembler cette expression régulière (parce que /\((.+),(.+)\)/ ne marche pas)

N'hésitez pas à me poser des question si ce n'est pas assez clair. Merci d'avance

[Flodelarab]

Bonjour

• Left() OK
  Right() OK
  Root() Admettons. (quoique inutile et/ou inhomogène)
  Left.Left() ? Késako ? ( Qu'est-ce ? )
  .
  
• De plus, 3 ne peut pas être le fils de 3 sinon, il y a un cycle et ce n'est plus un arbre.
  .

• Je code en Ruby donc je peux utiliser facilement la fonction "String#split" qui prends en argument une expression régulière.

  Oui mais ton expression régulière symbolise le séparateur .
  Ruby ne va pas parser ta chaîne.
  Tu es bon pour une récurrence. ou une récursivité.
  

  Code ruby :

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

  1
  2
  "1(7($,$),3($,3($,$)))".split(/[(,)]/)
  # => donne ["1", "7", "$", "$", "", "3", "$", "3", "$", "$"]

  .
• Si tu tiens aux regex, une autre idée :
  

  Code :

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

  1
  2
  3
  4
  $ grep --color '[^,()]\+([^,()]*,[^()]*)' <<<"root(left(left.left($,$),$),right($,$))"
  root(left(left.left($,$),$),right($,$))
  $ grep --color '[^,()]\+([^,()]*,[^()]*)' <<<"1(7($,$),3($,3($,$)))"
  1(7($,$),3($,3($,$)))

[johhry]

Bonjour @Flodelarab,

Merci pour votre réponse. Je m'explique plus clairement :

La représentation de ces arbres sont :

Code ruby :

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

0(-1($,$),9(3($,$),$))

Code ruby :

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

r(l($,ll($,$)),rr($,rrr($,$)))

Mais ça peut être n'importe quelle chaine (ou nombre, sauf le caractère représentant l'absence de noeud $)

C'est vrai que la solution ""1(7($,$),3($,3($,$)))".split(/[(,)]/)" peut marcher, il me suffira de parcourir cette liste recursivement en créant l'arbre.

Bonne soirée

[CosmoKnacki]

Tu peux utiliser une pattern récursive qui sera alors capable tout d'abord d'extraire la valeur du nœud, puis de différencier la partie gauche de la partie droite du nœud quelque soit la profondeur (\g<0> représente la pattern elle-même et permet donc la récursion):

Code ruby :

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

1
2
irb(main):001:0> "0(-1($,$),9(3($,$),$))".match(/(?<val>[^(),]+)\((?<left>\$|\g<0>),(?<right>\$|\g<0>)\)/)
=> #<MatchData "0(-1($,$),9(3($,$),$))" val:"3" left:"3($,$)" right:"9(3($,$),$)">

ensuite il suffit d'appliquer la même pattern sur les parties gauche et droite obtenues (jusqu'à aboutir à $).

Néanmoins, j'attire ton attention sur le fait que la pattern devra parser les mêmes morceaux de chaîne x fois (x dépendant de la profondeur de l'arbre).

D'un point de vue algorithmique, il est bien meilleur de tokenizer la chaîne:

Code ruby :

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

1
2
irb(main):005:0> "0(-1($,$),9(3($,$),$))".scan(/[^(),]+|./)
=> ["0", "(", "-1", "(", "$", ",", "$", ")", ",", "9", "(", "3", "(", "$", ",", "$", ")", ",", "$", ")", ")"]

puis de tester les tokens un par un pour savoir quoi faire.

Maintenant en pratique, je ne peux pas te dire lequel sera le plus performant, ni à partir de quel niveau de récursion Nokogiri (le moteur de regex de Ruby) te lâchera.