Solutions du TD-3, piles

1 Calculette polonaise

Voici les classes IntList, IntStack et HP.

Je vois peu à dire en plus du code...Il peut être intéressant d'aller voir du côté du TD-5 de l'année dernière et de sa solution. Le problème étant alors un peu différent (le programme de la calculette était donné par le premier argument de la ligne de commande).

2 Calculette américaine bas de gamme

Voici les classes StringList, StringStack et BasGamme.

Là encore, le code parle de lui même...On peut noter l'écriture de reduce avec une boucle ``infinie'', dont ont sort par return.

 static void reduce() {
    while (true) { // boucle sans fin
      String s = stackm.pop () ;    
      if (s.equals("+")) { // Addition, les autres cas sont pareils
        int i1 = stacki.pop ();
        int i2 = stacki.pop ();
        stacki.push (i2 + i1) ;
         .
         .
         .

      } else if (s.equals("[")) {
        return ;
      } else 
        stacki.push (Integer.parseInt(s));
    }
  }

On peu aussi remarquer le source particulièrement court de main (sans les affichages).

  public static void main (String [] arg) {
    for (int i = 0 ; i < arg.length ; i++) {
      String s = arg[i] ;
      if (s.equals("]"))
        reduce () ;
      else
        shift(s) ;
    }
  }
}

Un peu de culture tout de même. L'opération de retrouver une certaine structure dans une écriture linéaire est dite analyse syntaxique (parsing). Typiquement et dans le cas qui nous intéresse, toute ambiguité d'écriture est levée si on considère non plus des écritures du style ``1 + 2 x 3'' mais des arbres :

   +                    x
  / \                  / \
 1   x     ou         +   3
    / \              / \
   2   3            1   2

L'opération de parsing consiste à produire un arbre à partir de l'écriture linéaire. Cette opération, réalisée par un programme qui s'appelle analyseur syntaxique (parser), lève toute espèce d'ambiguité. Certes, dans notre cas on ne produisait pas d'arbre, on calculait à la place. Toutefois la structure d'arbre aide fortement à la compréhension de ce qui se passe : à tout instant la pile stacki contient le résultat de l'évaluation des sous-arbres analysés jusque là, tandis que la pile stackm contient les mots non encore exploités. Les sous-arbres (ou plutôt leur valeur) ont étés empilés lors d'une l'exploitation des mots et sous-arbres qui les fondent. (par ex. dans E₁ + E₂ donne l'arbre E, l'arbre E est créé en mangeant deux sous arbres et un mot.)

Le parenthésage complet expose la structure d'arbre sous-jacente sous une forme facilement exploitable à l'aide d'une pile. Chaque ouvrante délimitant un début d'un sous-arbre et chaque fermante une fin. Il suffira donc d'empiler les ouvrantes et de se débrouiller lorsque l'on rencontre une fermante pour retrouver et dépiler l'ouvrante correspondante, qui se trouve être la première sur la pile. Le parenthésage abusif a pour unique but d'identifier chaque sous-arbre à créer. Les parenthèses supplémentaires (genre [ [ 1 ] ]) ne servent à rien, mais ne font pas planter le programme.

Un calcul remplace ici une création de sous-arbre. (Cas de entier, création d'une feuille, et des opérateurs création de noeud iterne).

Mais la procédure la plus générale consiste à d'abord faire l'analyse syntaxique, puis toute espèce de travail utile. C'est intelligent, car :

L'analyse syntaxique est un domaine bien défriché, on dispose même d'outils automatiques pour créer un analyseur syntaxique à partir d'une spécification formelle du langage à reconnaître. Ces outils signalent les ambiguités et donnent parfois le moyen de les corriger simplement. Ainsi personne n'écrira un analyseur d'expressions infixes comme nous l'avont fait, mais utilisera plûtot yacc ou ocamlyacc. Un chapitre complet du poly traite de l'analyse syntaxique et n'épuise pas la question. Quelques notes de cours de la majeure compilation peuvent aussi être éclairants..
Les arbres autorisent ensuite toutes les audaces, alors que tout travail un tant soit peu compliqué sur la représentation linéaire est problématique.

3 Calculette américaine

Voici le source Texas. Par rapport à la précédente méthode main, le source a pris un peu de poids :

  public static void main (String [] arg) {
    shift("[") ; shift("[") ; shift ("[") ;
    for (int i = 0 ; i < arg.length ; i++) {
      String s = arg[i] ;
      if (s.equals("]")) {
        reduce () ; reduce () ; reduce () ;
        shift("[") ; shift("[") ;
      } else if (s.equals("+") || s.equals("-")) {
        reduce () ; reduce () ;
        shift(s) ;
        shift ("[") ; shift ("[") ;
      } else if (s.equals("x") || s.equals("/")) {
        reduce () ;
        shift(s) ;
        shift ("[") ;
      } else
        shift(s) ;
      System.out.println(s + " : " + stacki + "    " + stackm) ;
    }
    reduce () ; reduce () ; reduce () ;
  }

Vous remarquerez qu'il découle directement de l'énoncé. L'énoncé lui même repose sur l'astuce que l'on peut donner les priorités des opérateurs en ajoutant localement quelques empilages et dépilages. Notez que les parenthèses sont ici des sortes d'opérateurs.

Cette façon d'analyser les expressions infixes n'est pas standard... Il y a plus efficace. On peut en particulier définir des relations de précédence entre opérateurs et les utiliser pour savoir quand faire shift et jusqu'où faire reduce. C'est moins immédiat qu'il n'y paraît (voir une autre calculette TexasBis).

Une autre technique d'analyse utlisable ici est l'analyse LL (voir lea références ci-dessus). L'idée est que l'analyseur est un programme récursif qui reproduit la structure de la grammaire des expressions analysées. Le source LL réalise cette analyse.

4 Traduction

Voici le source Traduc.

À la lumière des remarques précédentes sur la dialectique entrée linéaire/arbre, on comprendra que l'on a imprimé un arbre sous forme postfixe, sans construire cet arbre : si il y a lieu, au moment de la fermeture d'une parenthèse de construire un noeud, il est largement temps d'afficher le symbole contenu dans ce noeud.

Pour ceux qui ne le savent pas, imprimer un arbre sous forme postfixe. consiste à parcourir l'arbre en affichant les symboles des noeuds dans l'ordre : afficher le fils gauche, le fils droit, afficher le symbole du noeud.

5 Il reste du temps

Deux classes Stack et NewHP.

Ce document a été traduit de L^AT_EX par H^EV^EA.