Fonction récursive pour obtenir un arbre

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

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, 18h00

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, 19h37

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, 20h24

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, 21h00

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, 21h02

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.

Fonction récursive pour obtenir un arbre

Langage Perl

Vue hybride

Discussions similaires

Partager

Partager