Discussion :

[nicolas66]

Bonjour,

Pour les besoins d'un projet, je dois arriver à transformer une chaine structurée en arbre n-iare en langage PHP.

Voici un exemple :

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
 
Chaine -> sujet(gn(pronom nom)) verbe cod(article nom)
Arbre n-aire résultat :
           racine
           / | \
          /  |  \
         /   |   \
        /    |    \
       /     |     \
    sujet  verbe   cod
      |             |
     gn             gn
     /\             /\
    /  \           /  \
   /    \         /    \
pronom  nom   article  nom

Pour la gestion des chaînes de caractères, de l'arbre et des noeuds, j'ai déjà écrit toutes les classes nécessaires. Il me reste à trouver l'algo. J'ai essayé d'y réfléchir mais je vois pas trop comment faire ca, à part peut-être avec une pile. Merci qd même à ceux qui pourront me filer un coup de pouce


Nico.

[ol9245]

quand tu ouvre une parenthèse, tu crée un niveau fils.
tant qu'il n'y a pas de parenthèse ouvrante ni fermante, tu crée des frères.
quand tu trouve une parenthèse fermante, tu remonte au père

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
r=racine
pour chaque mot m, faire :
    si mot == "(", 
        créer c = fils de r
        r = c
    sinon, si mot == ")",
        r = père de r
    sinon
        si r contient déja un mot, 
            créer f = frère de r
            r = f
        fin si
        attacher le mot m à r
    fin si
mot suivant

[Sylvain Togni]

Tu peux formuler le problème sous la forme d'une grammaire puis utiliser un algorithme d'analyse syntaxique tel que CYK.