Fonction récursive pour obtenir un arbre

Version imprimable

Bonjour à tous,

Problème :
Imaginons que j'aie un tableau tel que :

Code:

my @tab = ("h1","p","p","h1","p","h2","p","h1","p");

où :

h1 = titre de niveau 1
p = paragraphe
h2 = titre de niveau 2

J'aimerais obtenir un arbre tel que :
h1
---p
---p
h1
---p
---h2
--- ---p
h1
---p

de manière à ce que les "h1" soient coordonnés aux autres "h1", les "p" subordonnés au dernier "h_x" rencontré (et coordonnés entre "p") et les "h2" soient subordonnés aux "h1".

Dis autrement, à partir d'une séquence de scalaires représentant les éléments d'un document numérique, j'aimerais créer un arbre représentant la logique de ce document.

Ma première solution :
Il me paraît évident qu'il est nécessaire dans ce cas d'écrire une fonction récursive. Cependant, je cale à faire quelque chose qui fonctionne.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 my @tab = ( "h1", "p", "p", "h1", "p"); &recursiv(0, "root"); my $last_indice; sub recursiv { my ($indice, $previous) = @_; my $transition = &rules($indice, $previous); if($transition eq "sub"){ print "<div>\n"; my $new_indice = $indice + 1; $last_indice = &recursiv($new_indice, $tab[$indice]); print "</div>\n"; } elsif($transition eq "coord"){ print "\t<$tab[$indice]>\n"; print "\t</$tab[$indice]>\n"; } elsif($transition eq "up"){ # On remonte au dernier appel de la fonction return $indice; } } # h1 - p : subordonné # p - p : coordonné # p - h1 : on remonte sub rules{ my ($indice, $previous) = @_; if($tab[$indice] eq "h1" && $previous eq "root"){ return "sub"; }elsif($tab[$indice] eq "p" && $previous eq "h1"){ return "sub"; }elsif($tab[$indice] eq "p" && $previous eq "p"){ return "coord"; }elsif($tab[$indice] eq "h1" && $previous eq "p"){ return "up"; } }
Avez-vous un conseil à me donner?

D'avance, merci.

Une deuxième solution

Une solution plus avancée :
... mais qui fournit encore des erreurs.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 my @tab = ("h1","h2","p","p","h2","p","h1","p"); my $indice = 0; foreach(@tab){ if($_ eq "h1"){ print "<h1>\n"; &recur($indice+1, 1); print "</h1>\n"; } $indice++; } sub recur{ my ($i, $level) = @_; for($i;$i<=$#tab;$i++){ if($tab[$i] eq "p"){ print "\t" x $level ."<p>\n"; print "\t" x $level ."</p>\n"; } elsif($tab[$i] eq "h2"){ print "\t<h2>\n"; &recur($i+1, 2); print "\t</h2>\n"; last; } elsif($tab[$i] eq "h1"){ last; } } }
Résultat :
pour ("h1","h2","p","p","h2","p","h1","p")

<h1>
<h2>
<p>

</p>

<p>

</p>

<h2>

<p>

</p>

</h2>

</h2>
</h1>
<h1>

<p>

</p>
</h1>

Problème :
On voit nettement que la balise ne se ferme pas pour le "h2" (cf. code en rouge).

De même, j'aimerais aussi pouvoir traiter des objets tels que des listes qui contiendrait elle-même des éléments.

Par exemple :
("h1", "p","list","item1","item2")
donnerait :

<h1>
<p>
</p>
<list>

<item1>

</item1>

<item2>

</item2>
</list>
</h1>

Quelqu'un a un commentaire éclairé à me proposer?
D'avance merci.

29/05/2013, 19h37
Lolo78

Hmm, pas convaincu qu'une fonction récursive soit la solution la plus simple dans un tel cas.

A mon avis, une démarche itérative avec une variable stockant le niveau où tu te trouves sera plus simple.

Une première solution

Une première solution :
Avec du récursif.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
my @tab = ("h1","h2","p","p","h3","p","h1","p");
 
my $i=0;
&xml("root", 1);
 
my $var_temp;
sub xml{
	my ($previous_tag) = shift;
 
 
	if(defined($tab[$i])){
		my $current = $tab[$i];
 
		$var_temp = $i;
		if(&strictPlusPetit($current, $previous_tag)){
			print "<$current>\n";
 
			$i++;
			&xml($current);
 
			print "</$current>\n";		
			&xml($previous_tag);
 
		}
		else{
			$i = $var_temp;
		}
	}
}
 
 
 
sub strictPlusPetit{
	# Renvoie 1 si le tag courant est plus petit que le tag précédent
	my ($current_tag, $previous_tag) = @_;
 
	if($previous_tag eq "root"){
		return 1;
	}
	if($current_tag eq "root"){
		return 0;
	}
	if($current_tag eq "h1" && $previous_tag eq "h2"){
		return 0;
	}
	elsif($current_tag eq "h2" && $previous_tag eq "h1"){
		return 1;
	}
	elsif($current_tag eq "p" && $previous_tag eq "h1"){
		return 1;
	}
	elsif($current_tag eq "p" && $previous_tag eq "h2"){
		return 1;
	}
	elsif($current_tag eq "h3" && $previous_tag eq "h2"){
		return 1;
	}
	elsif($current_tag eq "p" && $previous_tag eq "h3"){
		return 1;
	}
	else{
		return 0;
	}
}

Deuxième solution :

Une deuxième solution :
Doublement récursive mais solution plus explicite dans la gestion de la pile.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
my @tab = ("h1","p","p","h1","h2","p","p","h2","p");
 
my @pile_vide = ();
&parcourirTab(\@pile_vide, 0);
 
sub parcourirTab{
	# Parcourt du tab
	my ($liste_bal_ouvert, $indice) = @_;
	my @pile = @$liste_bal_ouvert;
 
	# Cas d'arrêt
	if($indice > $#tab){
 
		# Fermeture des balises encore ouvertes
		# Petit hack pour l'identation.
		my @revert = reverse(@pile);
		my $taille = @revert;
		$taille--;
		foreach(@revert){
			print "\t" x $taille ."</$_>\n";
			$taille--;
		}
	}
	else{
		my $ref =	&toutImprim(\@pile, $tab[$indice]);
		&parcourirTab($ref,$indice+1);
	}
}
 
 
sub toutImprim{
	# Gère la pile
	# Fais toutes les impressions
	# et retourne la liste des balises ouvertes après son action.
 
	my ($liste_bal_ouvert, $balise_a_ouvrir) = @_;
	my @pile = @$liste_bal_ouvert;
 
	my $taille = @pile;
	# Si la pile est vide
	if($taille == 0){
		print "<$balise_a_ouvrir>\n";
		push(@pile, $balise_a_ouvrir);
		return \@pile;
	}
	else{
		my $var = pop(@pile);
		# Si strictement plus profond (petit)
		if(!&plusPetit($var, $balise_a_ouvrir)){
 
			my $taille_1 = @pile;
			$taille_1++;
 
			print "\t" x $taille_1 ."<$balise_a_ouvrir>\n";
			push(@pile, $var);
			push(@pile, $balise_a_ouvrir);
			return \@pile;
		}
		# Sinon, on ferme la première balise de la pile
		else{
			my $taille_2 = @pile;
			print "\t" x $taille_2 ."</$var>\n";
 
			&toutImprim(\@pile, $balise_a_ouvrir);
		}
	}
}
 
sub plusPetit{
	# Renvoie 1 si le tag courant est plus petit que le tag précédent
	# Renvoie 1 si le tag courant est égal au tag précédent
	my ($current_tag, $previous_tag) = @_;
 
	if($previous_tag eq "h2" && $current_tag eq "h1"){
		return 0;
	}
	elsif($previous_tag eq "p" && $current_tag eq "h1"){
		return 0;
	}
	elsif($previous_tag eq "h1" && $current_tag eq "h2"){
		return 1;
	}
	elsif($previous_tag eq "h1" && $current_tag eq "p"){
		return 1;
	}
	elsif($previous_tag eq "h2" && $current_tag eq "p"){
		return 1;
	}
	elsif($previous_tag eq "p" && $current_tag eq "h2"){
		return 0;
	}
	else{
		return 1;
	}

Si vous avez des améliorations, commentaires, n'hésitez pas.

29/05/2013, 21h02
TerrorOnCity
Et j'oubliais :

Ainsi, avec les deux solutions proposées, pour :

Code:

my @tab = ("h1","p","p","h1","h2","p","p","h2","p");

on obtient :
- <h1>
- <p>
- </p>
- <p>
- </p>
- </h1>
- <h1>
- <h2>
- <p>
- </p>
- <p>
- </p>
- </h2>
- <h2>
- <p>
- </p>
- </h2>
- </h1>
.. ouf. ;)
30/05/2013, 00h12
Lolo78

Je redis ce que j'ai déjà dit autrement: 91 lignes de codes, ça me paraît énorme pour un problème apparemment aussi simple. Une version itérative avec mémorisation des états doit pouvoir tenir en deux fois moins de code et être bien plus facile à comprendre.

Mais je me trompe peut-être, et, de toute façon, tu fais comme tu veux...
30/05/2013, 01h28
TerrorOnCity

Bonsoir,

C'est aussi ce que je pensais au début. Cependant, le problème n'est pas si facile qu'il en a l'air. Après s'être penché à plusieurs dessus avec quelques collègues, la solution à pile nous a paru la plus simple à implémenter. Revenir à un problème de parsing est, je pense, une bonne stratégie dans ce genre de problème.

L'ennui avec la solution itérative est qu'elle ne permettait pas de résoudre facilement les fermetures de balise. De plus, mais je peux me tromper, j'ai l'impression qu'elle s'avère assez simple lorsqu'il y a peu de règles, mais de plus en plus complexe, lorsque le nombre de types de balise augmente (h1, h2, ..., h.., quote, footnote, list, item, etc).

Cela dit, je suis loin d'être un expert en algorithmique et si quelqu'un a une solution plus élégante à proposer, ce serait avec plaisir que je la lirai et la communiquerai à ceux qui m'ont aidé pour les deux solutions proposées plus haut.
30/05/2013, 09h59
Philou67430
Question (piège) :
comment interpréter cette liste : "h1", "p", "h2", "p", "p" ?

Comme ceci :
Code:

1 2 3 4 5 h1 p h2 p p
ou bien comme ceci :
Code:

1 2 3 4 5 h1 p h2 p p
Ton problème est que : tu dois définir de manière formelle le schéma/la syntaxe de ton langage pour que ton parseur puisse reconstruire un arbre correctement. Dans le cas cité ici, le fait d'avoir "aplati" ce qui était initialement un arbre (html) fait perdre la notion d'imbrication, et rien ne définit apriori comment la reconstruire.
31/05/2013, 00h49
Lolo78

La réponse de Philou pose le problème: le cahier des charges n'est pas défini assez précisément.

En fait, la raison pour laquelle j'ai répondu en partie par des généralités sur ce qui me semble être la meilleure méthode est qu'en fait, je n'ai pas vraiment envie de m'impliquer dans un problème qui me paraît incomplètement défini.

Quand tu montres un exemple tu dis qu'il est fautif parce que l'indentation ou la balise fermante n'est pas là où tu l'attends, j'ai bien une idée de pourquoi tu dis cela, mais je ne suis pas sûr ce ce que tu attends à la place.

Bref, cahier des charges incomplet -> pas vraiment envie de m'impliquer, j'ai déjà trop donné sur ce genre de partition.