Piles et files

Point de départ

// ── Pile par tableau ──────────────────────────────────────────────────────
function creerPile() {
  const T = [];
  return {
    empiler: (x) => T.push(x),
    depiler: () => T.pop(),
    sommet: () => T[T.length - 1],
    estVide: () => T.length === 0,
    taille: () => T.length,
    contenu: () => [...T],
  };
}

// ── File par tampon circulaire ────────────────────────────────────────────
function creerFile(capacite) {
  const T = new Array(capacite).fill(null);
  let tete = 0, queue = 0;
  // ← il manque un compteur : sans lui, plein et vide sont indiscernables
  return {
    enfiler(x) {
      T[queue] = x;
      queue = (queue + 1) % capacite;
      return true;   // ← devrait refuser si la file est pleine
    },
    defiler() {
      const x = T[tete];
      tete = (tete + 1) % capacite;
      return x;      // ← devrait rendre undefined si la file est vide
    },
    estVide: () => false,   // ← à écrire
    estPleine: () => false, // ← à écrire
    contenu: () => T.map((v, i) => (v === null ? "." : v)).join(" "),
  };
}

// ── Application 1 : parenthésage ──────────────────────────────────────────
const PAIRES = { ")": "(", "]": "[", "}": "{" };

function verifier(texte) {
  const p = creerPile();
  for (let i = 0; i < texte.length; i++) {
    const c = texte[i];
    if ("([{".includes(c)) p.empiler({ c, i });
    else if (c in PAIRES) {
      // ← à écrire : trois cas d'erreur distincts à distinguer
    }
  }
  return { ok: true };
}

// ── Application 2 : expression postfixée ──────────────────────────────────
function evaluer(expression) {
  const p = creerPile();
  for (const jeton of expression.split(" ")) {
    if (!isNaN(Number(jeton))) { p.empiler(Number(jeton)); continue; }
    const a = p.depiler();
    const b = p.depiler();
    // ← attention à l'ORDRE : lequel de a et b est l'opérande de gauche ?
    if (jeton === "+") p.empiler(a + b);
    if (jeton === "-") p.empiler(a - b);
    if (jeton === "*") p.empiler(a * b);
    if (jeton === "/") p.empiler(a / b);
  }
  return p.depiler();
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Ajoutez le compteur à la file et faites-la refuser proprement.
// 2. Écrivez verifier() en distinguant les trois erreurs.
// 3. Corrigez l'ordre des opérandes dans evaluer().

for (const e of ["5 1 2 + 4 * + 3 -", "7 3 -", "20 4 /"]) {
  console.log(e.padEnd(22) + "= " + evaluer(e));
}

Solution

function creerPile() {
  const T = [];
  return {
    empiler: (x) => T.push(x),
    depiler: () => T.pop(),
    sommet: () => T[T.length - 1],
    estVide: () => T.length === 0,
    taille: () => T.length,
    contenu: () => [...T],
  };
}

function creerFile(capacite) {
  const T = new Array(capacite).fill(null);
  let tete = 0, queue = 0, nombre = 0;   // le compteur qui manquait
  return {
    enfiler(x) {
      if (nombre === capacite) return false;   // refuser plutôt qu'écraser
      T[queue] = x;
      queue = (queue + 1) % capacite;
      nombre++;
      return true;
    },
    defiler() {
      if (nombre === 0) return undefined;
      const x = T[tete];
      T[tete] = null;
      tete = (tete + 1) % capacite;
      nombre--;
      return x;
    },
    estVide: () => nombre === 0,
    estPleine: () => nombre === capacite,
    nombre: () => nombre,
    contenu: () => T.map((v) => (v === null ? "." : v)).join(" "),
  };
}

const PAIRES = { ")": "(", "]": "[", "}": "{" };

function verifier(texte) {
  const p = creerPile();
  for (let i = 0; i < texte.length; i++) {
    const c = texte[i];
    if ("([{".includes(c)) p.empiler({ c, i });
    else if (c in PAIRES) {
      // Erreur 1 : un fermant alors que rien n'est ouvert.
      if (p.estVide()) return { ok: false, quoi: "fermeture orpheline " + c, position: i };
      const ouvert = p.depiler();
      // Erreur 2 : un fermant qui ne correspond pas au sommet.
      if (ouvert.c !== PAIRES[c]) {
        return { ok: false, quoi: ouvert.c + " fermé par " + c, position: i };
      }
    }
  }
  // Erreur 3 : des ouvertures jamais refermées.
  if (!p.estVide()) {
    const reste = p.sommet();
    return { ok: false, quoi: reste.c + " jamais refermé", position: reste.i };
  }
  return { ok: true };
}

function evaluer(expression) {
  const p = creerPile();
  for (const jeton of expression.split(" ")) {
    if (!isNaN(Number(jeton))) { p.empiler(Number(jeton)); continue; }
    // Le PREMIER dépilé est l'opérande de DROITE : c'est le dernier empilé.
    const droite = p.depiler();
    const gauche = p.depiler();
    if (jeton === "+") p.empiler(gauche + droite);
    if (jeton === "-") p.empiler(gauche - droite);
    if (jeton === "*") p.empiler(gauche * droite);
    if (jeton === "/") p.empiler(gauche / droite);
  }
  return p.depiler();
}

console.log("— file circulaire —");
const f = creerFile(6);
for (const x of ["A", "B", "C", "D"]) f.enfiler(x);
console.log("   après 4 enfilages :", f.contenu(), "| nombre", f.nombre());
f.defiler(); f.defiler(); f.defiler(); f.defiler();
for (const x of ["E", "F", "G"]) f.enfiler(x);
console.log("   après 4 défilages puis 3 enfilages :", f.contenu(),
            "  (les positions 0 et 1 ont été RÉUTILISÉES)");
for (const x of ["H", "I", "J", "K"]) {
  if (!f.enfiler(x)) console.log("   file pleine : " + x + " refusé, rien n'est écrasé");
}

console.log("");
console.log("— parenthésage —");
for (const t of ["(a[b]{c})", "(a]b)", "a)b", "(a[b)", "((a)"]) {
  const r = verifier(t);
  console.log("   " + t.padEnd(12) + (r.ok ? "correct" : "INCORRECT : " + r.quoi + " (position " + r.position + ")"));
}

console.log("");
console.log("— expressions postfixées —");
for (const [e, attendu] of [["5 1 2 + 4 * + 3 -", 14], ["7 3 -", 4], ["20 4 /", 5], ["2 3 4 * +", 14]]) {
  const v = evaluer(e);
  console.log("   " + e.padEnd(22) + "= " + String(v).padStart(4) +
              (v === attendu ? "  ok" : "  X attendu " + attendu));
}
// « 7 3 - » est le test qui compte : en inversant les opérandes on obtient
// −4 au lieu de 4. L'addition et la multiplication ne l'auraient pas révélé,
// ce qui rend l'erreur facile à laisser passer.

Avant de commencer

• Le TP 5 : liste chaînée
• Le TP 1 : la pile d'appels

Énoncé

1. La pile, deux fois — Implémentez une pile sur tableau dynamique, puis sur liste chaînée. Même interface. Comparez les temps sur un million d'opérations.
2. La file, et le piège — Implémentez une file sur tableau simple, en avançant les deux indices. Faites tourner un million d'enfilages et défilages et observez la consommation mémoire.
3. Le tampon circulaire — Corrigez avec un tableau circulaire. Trouvez comment distinguer une file pleine d'une file vide, et implémentez votre choix. Indice : Les deux situations donnent les mêmes indices ; il faut une information de plus.
4. Vérifier un parenthésage — Écrivez la vérification d'une expression contenant trois sortes de délimiteurs. Testez sur des cas corrects, des cas mal fermés, et des cas mal imbriqués.
5. Évaluer une expression postfixée — Écrivez l'évaluateur, puis la conversion de l'infixe vers le postfixe. Testez sur une expression avec priorités et parenthèses.
6. L'échange qui change tout — Écrivez un parcours de labyrinthe en utilisant une pile. Puis remplacez la pile par une file, sans rien changer d'autre. Comparez les chemins trouvés.
7. Comprendre l'écart — Sur un labyrinthe où plusieurs chemins mènent à la sortie, dites laquelle des deux versions trouve le plus court, et pourquoi.
8. Au fil rouge — Ajoutez pile et file à votre bibliothèque, avec un en-tête propre et des tests. Vous les utiliserez telles quelles au TP 9.

C'est réussi quand

• ✓ Votre file circulaire tourne un million de fois sans croître en mémoire
• ✓ Votre évaluateur postfixé donne le bon résultat sur une expression à parenthèses
• ✓ Le passage pile → file change le chemin trouvé, et vous savez dire lequel est optimal

Correction

int file[1000000]; int debut = 0, fin = 0;
enfiler(v)  { file[fin++] = v; }
defiler()   { return file[debut++]; }

/* après un million d'opérations, debut = fin = 1 000 000
 la file est VIDE et le tableau est PLEIN :
 tout l'espace avant debut est perdu */

typedef struct { int *t; size_t cap, debut, taille; } File;

void enfiler(File *f, int v) {
  f->t[(f->debut + f->taille) % f->cap] = v;
  f->taille++;
}
int defiler(File *f) {
  int v = f->t[f->debut];
  f->debut = (f->debut + 1) % f->cap;
  f->taille--;
  return v;
}

int equilibre(const char *s) {
  Pile p; pile_init(&p);
  for (; *s; s++) {
      if (strchr("([{", *s)) empiler(&p, *s);
      else if (strchr(")]}", *s)) {
          if (pile_vide(&p)) return 0;              /* ferme sans ouvrir */
          char o = depiler(&p);
          if ((*s == ')' && o != '(') ||
              (*s == ']' && o != '[') ||
              (*s == '}' && o != '{')) return 0;    /* mal imbriqué */
      }
  }
  return pile_vide(&p);                             /* reste ouvert ? */
}

"3 4 + 2 *"
3    → empiler 3            pile : 3
4    → empiler 4            pile : 3 4
+    → dépiler 4 et 3, empiler 7    pile : 7
2    → empiler 2            pile : 7 2
*    → dépiler 2 et 7, empiler 14   pile : 14
résultat : 14

/* attention à l'ordre pour les opérateurs non commutatifs */
int b = depiler(&p), a = depiler(&p);   /* a AVANT b */
empiler(&p, a - b);

/* le seul changement */
Pile a_visiter;   →   File a_visiter;

avec une PILE : parcours en PROFONDEUR
suit un chemin jusqu'au bout avant d'essayer une autre branche
chemin trouvé : le premier, pas forcément le plus court
mémoire : la profondeur

avec une FILE : parcours en LARGEUR
explore par distance croissante depuis le départ
chemin trouvé : le PLUS COURT en nombre d'étapes — garanti
mémoire : la largeur, souvent bien plus grande