TD 2 — Piles et files

import java.util.NoSuchElementException;

class Pile<E> {
    private int tailleMax; // taille maximale de la pile
    private E[] contenu;   // éléments contenus dans la pile
    private int sommet;    // position du sommet dans le tableau

    @SuppressWarnings("unchecked")
    public Pile(int taille) {
        this.tailleMax = taille;
        this.contenu = (E[]) new Object[taille];
        this.sommet = -1; // convention : la pile est vide
    }

    public boolean isEmpty() {
        return sommet == -1;
    }

    public boolean isFull() {
        return sommet == tailleMax - 1;
    }

    public void push(E val) {
        if (isFull()) {
            throw new IllegalStateException("Pile pleine");
        }
        contenu[++sommet] = val; // on avance, puis on écrit
    }

    public E pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Pile vide");
        }
        return contenu[sommet--]; // on lit, puis on recule
    }

    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Pile vide");
        }
        return contenu[sommet];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[bas ");
        for (int i = 0; i <= sommet; i++) {
            sb.append(contenu[i]);
            if (i < sommet) {
                sb.append(", ");
            }
        }
        return sb.append(" haut]").toString();
    }
}

import java.util.NoSuchElementException;

class File<E> {
    private E[] contenu;    // éléments contenus dans la file
    private int tete;       // position de la tête dans le tableau
    private int nbElement;  // nombre d'éléments dans la file

    @SuppressWarnings("unchecked")
    public File(int taille) {
        this.contenu = (E[]) new Object[taille];
        this.tete = 0;
        this.nbElement = 0;
    }

    public boolean isEmpty() {
        return nbElement == 0;
    }

    public boolean isFull() {
        return nbElement == contenu.length;
    }

    public boolean offer(E t) {
        if (isFull()) {
            throw new IllegalStateException("File pleine");
        }
        contenu[(tete + nbElement) % contenu.length] = t;
        nbElement++;
        return true;
    }

    public E poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("File vide");
        }
        E t = contenu[tete];
        tete = (tete + 1) % contenu.length; // la tête « tourne »
        nbElement--;
        return t;
    }

    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("File vide");
        }
        return contenu[tete];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[tête ");
        for (int i = 0; i < nbElement; i++) {
            sb.append(contenu[(tete + i) % contenu.length]);
            if (i < nbElement - 1) {
                sb.append(", ");
            }
        }
        return sb.append(" queue]").toString();
    }
}

public static boolean verifDelim(String s) {
    int compteur = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            compteur++;
        } else if (c == ')') {
            compteur--;
            if (compteur < 0) {
                return false; // une fermante de trop, avant toute ouvrante
            }
        }
    }
    return compteur == 0; // toutes les ouvertes ont été fermées
}

private static boolean correspond(char ouvrant, char fermant) {
    return (ouvrant == '(' && fermant == ')')
            || (ouvrant == '[' && fermant == ']')
            || (ouvrant == '{' && fermant == '}');
}

public static boolean verifDelimStack(String s) {
    Pile<Character> pile = new Pile<>(s.length() + 1);
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            pile.push(c); // on retient l'ouvrant
        } else if (c == ')' || c == ']' || c == '}') {
            if (pile.isEmpty()) {
                return false; // fermante sans ouvrante
            }
            if (!correspond(pile.pop(), c)) {
                return false; // mauvais type de fermant
            }
        }
    }
    return pile.isEmpty(); // des ouvrants restent ? chaîne invalide
}

public static boolean verifDelimDetail(String s) {
    Pile<Integer> pile = new Pile<>(s.length() + 1);
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            pile.push(i); // on retient OÙ l'ouvrant a été lu
        } else if (c == ')' || c == ']' || c == '}') {
            if (pile.isEmpty()) {
                // une fermante, mais aucune ouvrante en attente
                System.out.println("  indice " + i + " : « " + c + " » fermante sans ouvrante");
                return false;
            }
            int j = pile.pop();
            char ouvrant = s.charAt(j);
            if (!correspond(ouvrant, c)) {
                // on s'arrête au premier problème : la suite n'aurait plus de sens
                System.out.println("  indice " + j + " : « " + ouvrant
                        + " » fermé par « " + c + " » (indice " + i + ")");
                return false;
            }
        }
    }
    if (!pile.isEmpty()) {
        int j = pile.pop();
        System.out.println("  indice " + j + " : « " + s.charAt(j) + " » jamais fermé");
        return false;
    }
    return true;
}

« a[b(c)}d » :
  indice 1 : « [ » fermé par « } » (indice 6)
« {a(b[c[d))]e]} » :
  indice 6 : « [ » fermé par « ) » (indice 8)
« (a[b]c » :
  indice 0 : « ( » jamais fermé

public static void main(String[] args) {
    Pile<Integer> p = new Pile<>(3);
    p.push(1);
    p.push(2);
    p.push(3);
    System.out.println(p.isFull());  // true
    System.out.println(p.peek());    // 3
    System.out.println(p.pop());     // 3
    p.push(4);                       // réutilise la case libérée
    System.out.println(p);           // [bas 1, 2, 4 haut]

    File<String> f = new File<>(3);
    f.offer("a");
    f.offer("b");
    f.offer("c");
    System.out.println(f.poll());    // a
    f.offer("d");                    // tourne dans le tableau
    System.out.println(f);           // [tête b, c, d queue]

    String[] exemples = { "a(b)c", "a[b(c)}d", "{a(b[c[d))]e]}", "{a(b(d[d]))e}", "(a[b]c" };
    for (String s : exemples) {
        System.out.println(s + " -> " + verifDelimStack(s));
    }
}