Fonction récursive pour obtenir un arbre

**TerrorOnCity** · 29/05/2013, 18h11

Bonjour à tous,

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

Code :

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

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 :

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

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.

**TerrorOnCity** · 29/05/2013, 19h00

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

Code :

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

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.

**Lolo78** · 29/05/2013, 20h37

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.

**TerrorOnCity** · 29/05/2013, 21h24

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

Code :

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

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;
	}
}

**TerrorOnCity** · 29/05/2013, 22h00

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

Code :

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

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.

**TerrorOnCity** · 29/05/2013, 22h02

Et j'oubliais :

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

Code :

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

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.

**Lolo78** · 30/05/2013, 01h12

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...

**TerrorOnCity** · 30/05/2013, 02h28

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.

**Philou67430** · 30/05/2013, 10h59

Question (piège) :
comment interpréter cette liste : "h1", "p", "h2", "p", "p" ?

Comme ceci :

Code :

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

ou bien comme ceci :

Code :

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

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.

**Lolo78** · 31/05/2013, 01h49

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.

Fonction récursive pour obtenir un arbre

Langage Perl

Discussions similaires

Partager

Partager