Générer une chaine correctement parenthésée Résolu

Question

Bonjour,

On m'a donné cet algorithme et on me demande de le traduire en C, sauf que c'est un peu difficile :

p = PileVide()

tant que non Vide(p) 
      choisir entre:
      { c est une parenthèse ouvrante }
	  c = parenthèse ouvrante
	  Empiler(p , c)
       c est une parenthèse fermante }
	  si non Vide(p) alors
	     c = parenthèse fermante correspondant à Sommet(p)
             Dépiler(p)
      { c est un caractère peu importe}
	  c = caractère qui n'a pas de parenthése
      afficher c

... dans lequel :

PileVide est une fonction qui crée une pile vide ;
	Vide est une fonction qui renvoie true si et seulement si la pile est vide.

Voici par exemple des résultats valides :

(a(bvcbn))
(aevvjbb(er(yhh)))

Je ne sais pas si l'algorithme qu'on m'a donné est complet, car je ne vois pas comment il peut de générer une chaîne bien parenthésée.

Voici mes idées :

Pour l'histoire de choisir, ça me rappelle switch(..) en C
	Pour générer un texte aléatoirement je crois qu'on peut faire :

char chaine = "abcdefghijklmnopqrstuvwxyz";
char chaine aleatoire[26] = " ";
chaine aletatoire = chaine[rand() % 26];

Theo_0055 · Answer

typedef enum {
  Ouvrante,
  Fermante,
  Quelconque
} caractere;

?

Theo_0055 · Answer

en fait il faut que la fonction renvoie par exemple (a(bvcbn)) ou (aevvjbb(er(yhh))) .Il doit générer un texte bien parenthésé de façon aléatoire

Utilisateur anonyme · Answer

Soit.

Mais.

Par exemple, ce texte

on suppose que il existe une fonctioon appelée Pilevide qui vide crée une pile vide et  vide qui renvoie un bool ,si true alors la pile est vide sinon elle ne l'est pas

Et ces morceaux d'algorithme

p = PileVide()

tant que non Vide(p)
   '...
   Empiler(p , c)
   '...
   Dépiler(p)

p est donc un bool, donc

il ne peut pas être vide, un bool c'est true ou false, jamais vide,
	on ne peut pas non plus l'empiler ou le dépiler.

Et puis, après vérification dans plusieurs dictionnaires, l'adjectif (ou le participe passé) "parenthésé" n'existe pas, algorithme est masculin, comme te l'a fait remarquer Phil (que je salue).

Bref, entre ce qu'on doit deviner de ton texte et l'algorithme, rien n'est cohérent.

Theo_0055 · Answer

Ah mon truc est marqué resolu mais non

ah bon ce mot n'existe pas,pourtant dans mon énoncé ils ont ecrit bien parenthésé ...

J'ai pas fait attention a ces erreurs de frappe

je voulais dire Pilevide est une fonction qui crée une pilevide et Vide(p) est une fonction qui verifie si une pile est vide ou pas.Si elle l'est,elle renvoie true sinon false

j'ai essayé d'ecrire ceci mais rien ne se passe lorsque j'essaye de tester

char generer_parenthese_ouvrante(int n){
  if (n == 0)
    return '(';
  else if (n == 1)
    return '[';
  else
    return '{';
}

char generer_parenthese_fermante(int n){
  if (n == 0)
    return ')';
  else if (n==1)
    return ']';
  else
    return '}';
}

void generer_texte_bien_parenthese(){
  char chaine[26] = "abcdefghijklmnopqrstuvwxyz";
  PileCaractere p = creer_pile(&p);
  char c;
  int n;
  
  while(!est_vide(&p) ){
    printf("Valeur de n:");
    scanf("%d
", &n) ;
    printf("Valeur de c:");
    scanf(" %c", &c);
    switch (c) {
    case Ouvrante:
      c = generer_parenthese_ouvrante(n);
      empiler(&p,c);
      break;
    case Fermante:
      c = generer_parenthese_fermante(n);
      if(!est_vide(&p) )
        c = sommet(&p);        
      break;
    case Quelconque:
      c = chaine[rand() % 26];
      break;
   }
 }
 printf("%c", c);
}

Theo_0055 · Answer

en fait je sais pas comment dans le cas de case initialiser des trucs comme ça

peut etre dois etre char Ouvrante,Fermante,Quelconque

ou peut etre créer un type énuéré typdef enum{Ouvrante,Fermante,Quelconque}

Pourtant j'ai expliqué,j'ai dit que je dois traduire en C l'algorithme qu'on m'a donné pour qu'il génére un texte avec le bon nombre de parenthése ouvrante et fermante

Ex:(ab(cd)) ou ( { gh) }

Theo_0055 · Answer

cet algorithme n'est pas déterministe,il y a 2 choix à faire A chaque pas de l'itération  ,

-dois t-on encore afficher d'autres caractéres ou bien s'arreter?

-si on continue,quesce que tu dois afficher

Ces choix ne sont pas dit dans l'algorithme donc :

-Tu dois dire dans ton code quel choix tu as fait pour générer une chaine bien parenthésé (bon dans mon énoncé ils l'ont dit comme ça) et avec un niveau minimum d'imbrication

Theo_0055 · Answer

Mais ce que vous m'expliquez, c'est quand la chaîne générée est mal formée (pas le bon nombre de parenthèses ouvrantes / fermantes). En vrai de vrai, ça correspond à mon deuxième exercice mais pas le premier. Il faut que ma fonction génère un texte bien formé, c'est-à-dire avec le bon nombre d'ouvrantes et fermantes.

Theo_0055 · Answer

oui pour le truc du tableau c'est ça que j'ai essayé de faire dans mon code

char chaine[26] = "abcdefghijklmnopqrstuvwxyz";
c = chaine[rand()%26];

Bref,  mon soucis c'est surtout comment générer ce texte avec le bon nombre de parenthèses ouvrantes et fermantes en utilisant une pile, c'est-à-dire en utilisant l'algorithme que j'ai donné dans mon post du début.

Le faire sans l'algorithme est plus facile mais utiliser la pile non.

Et moi-même je ne comprends pas trop ce que fait l'algorithme ,j'ai juste essayé de la traduire en C.

Utilisateur anonyme · Answer

Quoi qu'il en soit, ton énoncé n'est pas cohérent.

Par exemple

{ c est un caractère peu importe}
	  c = caractère qui n'a pas de parenthése
      afficher c //ça veut dire qu'on n'ajoute pas c à la pile et donc la pile ne peut contenir que des parenthèses

Peux-tu vérifier, que tu l'as correctement retranscrit, mot pou moi et si

oui le confirmer
	non, le recopier exactement

Theo_0055 · Answer

ok

L'énoncé complet:

L'algorithme suivant (voir algorithme de mon message #1) permet de générer une chaîne bien équilibré. On utilise la pile pour sauvegarder l'état courant du parenthésage.

Cet algorithme n'est pas déterministe : il y a 2 options à faire à chaque pas de l'itération :

affiche-t-on encore des caractères ou bien s'arrête-t-on ?
	si on continue, quel type de caractère affiche-t-on ?

La manière de faire ces choix n'est ici pas indiquée. On peut pour cela utiliser un générateur aléatoire (tout en s'assurant que la chaîne générée est bien parenthésée).

Préciser les choix effectués dans l'algorithme ci-dessus afin de générer une chaîne aléatoire bien parenthésée d'une longueur minimum donnée.
	Préciser les choix effectués dans l'algorithme ci-dessus afin de générer une chaîne aléatoire bien parenthésée d'un niveau minimum d'imbrication donné

Utilisateur anonyme · Answer

Bien, mais l'algorithme que tu donnes ne correspond pas à ça, voir mon  "par exemple" du message 17.

Donc peux-tu vérifier que tu as correctement retranscrit l'algorithme mot pour mot ?

Theo_0055 · Answer

L'algorithme sans modification de ma part :

p = PileVide()

tant que non EstVide(p) ou il reste des caractères à imprimer
      choisir parmi :
      { c est une parenthèse ouvrante }
	  c = parenthèse ouvrante
	  Empiler(p , c)
      { c est une parenthèse fermante }
	  si non EstVide(p) alors
	     c = parenthèse fermante correspondant à Sommet(p)
             Dépiler(p)
      { c est un caractère quelconque }
	  c = caractère non parenthèse
      Afficher c

Utilisateur anonyme · Answer

OK, donc on peut conclure que

Il n'est jamais question de crochet ou d'accolade (comme tu l'as codé plus haut) dans l'algo, ni dans l'énoncé, donc pour l'instant, on oublie ces caractères.
	Les caractères "quelconques" ne sont jamais empilés, juste affichés.
	Il n'est pas écrit que les parenthèses sont affichées dans l'algo, pourtant selon l'énoncé elles le doivent.

Tes premières étapes sont donc d'écrire les fonctions

PileVide()
	EstVde()
	Empiler()
	Depiler()

Qui correspondent à l'énoncé, à l'algo et aux conclusions ci-dessus.

[Dal] · Answer

Bon, donc, il est clair que p n'est pas un booléen et si l'algo ne correspond pas aux indications textuelles, c'est que les indications donnent simplement d'autres indications additionnelles à prendre en compte.

Aussi, l'exercice est à faire avec une pile, donc, il doit le faire avec une pile et pas un compteur.

Comme le remarque Whismeril, note que, dans l'énoncé textuel que tu nous donnes en plus de l'algo, on ne parle que de parenthèses. Pour moi les parenthèses c'est ( ou ) et c'est tout. Pas [ ], ni { } ou autres. Si tu dois traiter ces types de caractères en plus, cela se complique un peu.

La pile sert juste à empiler les parenthèses ouvrantes. Lorsqu'une parenthèse fermante doit être écrite, la parenthèse ouvrante au sommet doit être retirée. Lorsqu'on a une pile vide, c'est qu'on a traité toutes les parenthèses. C'est, en gros, la seule chose que dit la partie des indications sous forme d'algo (incomplet à dessein).

À mon sens, vu la tête des deux premières lignes de l'algorithme, il ne peut marcher que si le texte commence par une parenthèse (comme une ligne d'instructions en langage Lisp et ses dérivés) :

p = PileVide()

tant que non Vide(p)

Donc, entre les deux lignes ci-dessus, il faudrait mettre sur la pile une parenthèse ouvrante, pour que l'algo exécute la boucle tant que (et afficher cette parenthèse ouvrante histoire de voir où on en est), et probablement indiquer que ce choix de conception a été fait.

Si on fait différemment, et que la ligne peut commencer par autre chose, il faudra insérer plus de code entre ces deux lignes de l'algo pour y mettre une boucle tant que l'on n'a pas inséré au moins une parenthèse ouvrante (et sans doutes cette boucle ne pourra générer que un caractère quelconque ou une parenthèse ouvrante, et pas terminer, sinon on aura une ligne sans parenthèses... et ce n'est pas le but de l'exercice a priori).

Tout cela ce sont des choix de conception.

Ensuite, les indications textuelles de l'énoncé sont importantes pour comprendre quels types de stratégie mettre en oeuvre, pour insérer dans le fonctionnement de l'algo les éléments nécessaires à la construction de la chaîne :

Cet algorithme n'est pas déterministe : il y a 2 options à faire à chaque pas de l'itération :

affiche-t-on encore des caractères ou bien s'arrête-t-on ?
    si on continue, quel type de caractère affiche-t-on ?

La manière de faire ces choix n'est ici pas indiquée. On peut pour cela utiliser un générateur aléatoire (tout en s'assurant que la chaîne générée est bien parenthésée).

Une fois que l'on a commencé avec une parenthèse ouvrante et qu'on entre dans la boucle de l'algorithme, on peut donc utiliser des tirages aléatoires avec rand() pour décider :

si on affiche encore des caractères ou si on s'arrête (un tirage retournant 0 ou 1 qui s"évaluent à faux et vrai respectivement en C)
	si on s'arrête, cela signifie qu'on doit fermer immédiatement toutes les parenthèses jusqu'à ce que la pile soit vide et c'est tout
	si on continue, on peut continuer avec 3 types de caractères comme l'a identifié 
	Theo_0055 (un autre tirage retournant 0, 1, ou 2 peut être fait), et un enum tel que l'a proposé Theo_0055 convient parfaitement, car l'enum est un type entier qui par défaut commencera à 0 et le résultat du tirage pourra être traité avec un switch / case utilisant les membres de l'énumération pour avoir un code plus parlant

Theo_0055, est-ce plus clair ?

Theo_0055 · Answer

Ok faisons avec juste les parenthèse, et après, si je comprends avec un type, peut-être je pourrais le faire les autres.

Moi aussi cette ligne m'a perturbé un peu car si je suis sensé rentrer dans ma boucle, ma pile n'est pas sensé être vide. Or la fonction d'avant crée une pile vide. Vous avez raison, la solution est d'empiler d'abord une parenthèse ouvrante pour éviter que la pile soit vide dés le départ.

Donc, entre les deux lignes ci-dessus, il faudrait mettre sur la pile une parenthèse ouvrante, pour que l'algorithme entre dans la boucle while (et afficher cette parenthèse ouvrante histoire de voir où on en est), et probablement indiquer que ce choix de conception a été fait.

Par exemple dans la boucle while

int random = rand() % (1 - 0 + 1) = rand() % 0

Est-ce que mettre ça est correct ? Je veux que rand tire un nombre entre 0 et 1

Si c'est 0 qu'il retourne alors on s'arrête.
	
		Si on s'arrête alors on affiche des parenthèses fermantes jusqu'à ce que le nombre de parenthèses fermantes soit égal au nombre de parenthèses ouvrantes

Sinon on continue

Oui pour la suite c'est plus clair. Je veux utiliser correctement mon enum. Mais j'ai remarqué que si je fais :

switch(caractere)

où caractere a pour type mon enum, ça ne marche pas. Pourtant ça devrait.

Theo_0055 · Answer

Je viens de comprendre pourquoi ça ne marchait pas. C'est parce que mon enum caractere (que j'ai renommé caractere) je l'ai écrit directement dans mon switch sans le déclarer.

J'au aussi testé:

caractere c; 
switch(c) {
  ...
}

Ceci ne marchait pas non plus, car c ne contenait rien du tout.

Ok j'ai saisi

Pour le case Ouvrante:

empiler(&p, '(');
afficher_pile(&p);

Pour le case Fermante :

depiler(&p, '(');
afficher_pile(&p);

Pour le case Quelconque : Est ce que ma manière de procéder pour tirer un caractère est bonne ?

Theo_0055 · Answer

Ah oui c’est plus simple de faire printf(‘’ %c’’,c),c pour le caractère en question

maintenant j’ai compris ce qu’il fallait faire,merci

Maintenant je veux gérer le cas des crochets et accolades ,esceque ce que j’avais fait au début c’est à dire une fonction qui génère une Ouvrante selon le fait que je tire au hasard un 0,1 ,ou autre chose est bon

Si c’est 1 on génère une parenthèse,si c’est 1 un crochet sinon une accolade

Cette méthode choisi est elle pertinente?

par exemple je tire

Theo_0055 · Answer

Je vois : je peux pas fermer avec n'importe lequel. Il faut vérifier ce qu'il y a au sommet de la pile.

Si par exemple, j'ai une accolade ouvrante au niveau du sommet, lorsque je la dépile; il faut que j'affiche une accolade fermante pour la fermer.

Je ne peux pas par exemple générer un caractère fermant au hasard car si c'est une parenthèse fermante, l'accolade ouvrante ne sera pas fermée

Est-ce que c'est cela que vous vouliez dire ?

Theo_0055 · Answer

Ok je vais essayer de faire le code et je reviendrais ici le mettre

Utilisateur anonyme · Answer

Bonjour

une option peut être quand tu affiches ( tu empiles ), quand tu affiches { tu empiles } et donc au moment de dépiler, tu as directement la bonne fermeture.

Theo_0055 · Answer

@whismeril et @Dal j'ai fait ceci:

void empiler(PileCaractere *p, char x) {
  p->tab[p->n] = x;
  p->n = p->n + 1;
}

char depiler(PileCaractere *p) {
  p->n = p->n - 1;
  return p->tab[p->n];
}

char sommet(PileCaractere *p) { 
  return p->tab[p->n - 1]; 
}

char ouvrante_to_fermante(char ouvrante) {
  if (strcmp(ouvrante,'(') == 0)
    return ')';
  else if (strcmp(ouvrante,'{') == 0)
    return '}';
  else if (strcmp(ouvrante,'[') == 0)
    return ']'
}

void generer_texte_bien_parenthese() {
  char chaine[26] = "abcdefghijklmnopqrstuvwxyz";
  char ouvrant[3] = "({[";

PileCaractere p = PileVide(&p);
  char random_ouvrant = ouvrant[rand() % 3];
  empiler(&p, random_ouvrant);
   
  while(!est_vide(&p)) {
    enum type_de_caractere suivant = rand() % 3;
    switch (suivant) {
      case Ouvrante:
        empiler(&p, random_ouvrant);
        printf("%c", random_ouvrant);
        break;
      case Fermante:
        char fermante = ouvrante_to_fermante(sommet(&p))
        printf("%c", fermante);
        break;
      case Quelconque:
        c = chaine[rand() % 26];
        printf("%c", c);
        break;
    }
  }
}

Utilisateur anonyme · Answer

L'as tu testé?

Je pense qu'il manque un truc au moment de fermer.

Theo_0055 · Answer

Non pas encore testé

au moment de fermer vous vouliez dire quoi?

Theo_0055 · Answer

Ah ouais j'ai oublié d'écrire :

depiler(&p, sommet(&p));

Theo_0055 · Answer

Ah oui non c'est fini j'ai plus de questions

Merci a tous pour votre aide

Générer une chaine correctement parenthésée

25 réponses

Votre réponse

Discussions similaires

Newsletters