Discussion :

[deuzef68]

Bonjour

dans le cadre d'un petit projet perso j'aurai besoin de programmer un mini analyseur de texte.
Dans le programme on doit pouvoir entrer une chaine de texte...
codé suivant une codification simple mais précise.

Par exemple si on entre "A(B)2" cela doit générer en sortie "ABB" ...les parenthèses et le "2" donne le nombre de répétitions
Autre exemple "A((B)2C)2 en sortie o aura "ABBCBBC"

A noter que pour l'instant cette codification n'est pas encore totalement figée et pourrait évoluer suivant vos réponses
il y a peut être une codification plus "lisible"...comme dans lex peut être...
il ne devrait y avoir je pense que la notion de répétition...
peut être en plus faudrait il une notion de symétrie du style "ABCCBA" mais je ne vois pas trop comment la codifier...donc à voir...

Donc j'avais pensé me tourner vers lex et yacc... j'en ai un peu fait mais il y a très longtemps...vraiment très longtemps...
c'est peut être aussi utiliser un canon pour tuer une mouche... je n'ai pas assez de recul pour dire si c'est le bon choix...

A ce stade je recherche des idées...des pistes...
il existe peut être une autre voie...

j'attends vos réponses
D'avance merci

Fred

[ternel]

Ca ressemble à une expression régulière.
Si tu veux le coder à la main, l'idée principale, c'est qu'une telle chaine est constitué de deux choses:

1. des segments de lettres, tels que AAB
2. un enchainement de segments, comme .(.)2(.)((.)2.)4

Il y a au moins deux structures à définir:
le segment, qui contient assez d'information pour représenter un segment de taille arbitraire:

Code :

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

1
2
3
4
5
6
7
typedef struct segment {
    char* valeur;
} segment;
 
segment creer_segment(const char*);//strlen, malloc, strcpy
segment copier_segment(segment const*);
void détruire_segment(segment);//free de .valeur

Vient ensuite une structure qu'il faut penser soigneusement, pour représenter la structure.
Tu remarqueras qu'il y a deux constructions: la séquence et la répétition.

Je pense qu'il faut définir la chaine de commande comme un emboitement récursif de séquences et de répétition.
Il faut bien s'arreter à un moment, je suggère qu'une répétition ne concerne que des séquences

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
typedef struct sequence sequence;
typedef struct repetition {
    sequence seq; //pointeur?
    unsigned int n;
} repetition;
 
struct sequence {
    union {segment, repetition} contenu;
    enum {sequence_simple, sequence_complexe} est_simple;
    sequence * suite
};
 
sequence* creer_sequence_simple(segment);
sequence* creer_sequence_complexe(repetition);
void enchainer_sequence(sequence*, sequence*);
void detruire_sequence(sequence*);//libère toute la séquence, mais laisse à l'utilisateur de la fonction le soin de mettre le pointeur à NULL.

Reste à coder une première fonction sequence* analyser_format(const char*) pour transformer (et valider) la chaine de controle fournie par l'utilisateur.

Si tu envisage explicitement de n'avoir jamais deux lettres cote à cote dans la commande (c'est dommage), tu peux te passer de segment, et utiliser un simple char à la place.

[ternel]

Si ton besoin s'arrête là, tu devrais chercher une bibliothèque d'expressions régulières, comme décrite par exemple dans cet article de Nicolas Joseph.

[picodev]

Bonsoir,

Cela ressemble aussi à une simple calculatrice. Notons :

• + l'opérateur de concaténation
  "A" + "B" = "AB"
  
• * l'opérateur de répétition
  "A" * 4 = 4 * "A" = "AAAA"
  
• rev() la fonction d'inversion
  rev("ABC")="CBA"
  
• ... tout ce que tu peux imaginer ... head, tail, split, count, ...

Ce que tu écris comme : A((B)2C)2
deviendrait : A + 2 * ( B + 2 * C ) = A + 2 * (B + CC) = A + 2 * BCC = A + BCCBCC = ABCCBCC
deviendrait : A + 2 * ( 2 * B + C ) = A + 2 * (BB + C) = A + 2 * BBC = A + BCCBCC = ABBCBBC


La grammaire se formalise aisément et une implémentation peut se faire simplement avec le couple flex/bison. De souvenir il y a un exemple de calculatrice simple dont tu pourrais t'inspirer.

edit : désolé, j'ai mal interprété ton expression ... comme quoi il vaut mieux utiliser un parser ^^

[deuzef68]

Bonsoir

effectivement je n'avais pensé à l'aspect "mathématique" du formalisme...
et donc cela ressemble à une calculette
bien vu

je vais fureter un peu sur google...

Merci déjà...
si quelqu'un a d'autres idées, je suis preneur

Fred

[Invité]

Bien le bonsoir,

Pour apporter ma petite pierre à l'édifice, qui vaut ce qu'elle vaut...

Pourquoi ne pas passer par un arbre binaire ? C'est typiquement le genre de cas dans lequel on peut aisément les utiliser.

On construit l'arbre en parcourant récursivement la chaîne de caractère. Une fois celui-ci construit, "il suffit" de repasser dessus récursivement pour en calculer la chaîne finale.

En prenant l'équation A((B)2C)2 donné en exemple, cela donnerait un arbre binaire du genre :



Qui, une fois reconvertis, donnerait bien ABBCBBC.