Evaluation des expressions arithmétiques préfixées

Dans cette section, on illustre l'utilisation des piles par un programme d'évaluation d'expressions arithmétiques écrites de façon particulière. Rappelons qu'expression arithmétique signifie dans le cadre de la programmation: expression faisant intervenir des nombres, des variables et des opérations arithmétiques (par exemple: + * / - Ö ). Dans ce qui suit, pour simplifier, nous nous limiterons aux opérations binaires + et * et aux nombres naturels. La généralisation à des opérations binaires supplémentaires comme la division et la soustraction est particulièrement simple, c'est un peu plus difficile de considérer aussi des opérations agissant sur un seul argument comme la racine carrée, cette généralisation est laissée à titre d'exercice au lecteur. Nous ne considérerons aussi que les entiers naturels en raison de la confusion qu'il pourrait y avoir entre le symbole de la soustraction et le signe moins.

Sur certaines machines à calculer de poche, les calculs s'effectuent en mettant le symbole d'opération après les nombres sur lesquels on effectue l'opération. On a alors une notation dite postfixée. Dans certains langages de programmation, c'est par exemple le cas de Lisp ou de Scheme, on écrit les expressions de façon préfixée c'est-à-dire que le symbole d'opération précède cette fois les deux opérandes, on définit ces expressions récursivement. Les expressions préfixées comprennent:

• des symboles parmi les 4 suivants: + * ( )
  
• des entiers naturels
  

Une expression préfixée est ou bien un nombre entier naturel ou bien est de l'une des deux formes:

(+ e₁ e₂) (* e₁ e₂)
où e₁ et e₂ sont des expressions préfixées.

Cette définition fait intervenir le nom de l'objet que l'on définit dans sa propre définition mais on peut montrer que cela ne pose pas de problème logique. En effet, on peut comparer cette définition à celle des nombres entiers: ``tout entier naturel est ou bien l'entier 0 ou bien le successeur d'un entier naturel''. On vérifie facilement que les suites de symboles suivantes sont des expressions préfixées.

47
(* 2 3)
(+ 12
(+ (* 2 3) (+ 12 )
(+ (* (+ 35 36) (+ 5 6)) (* (+ 7 (* 9 9)))
Leur évaluation donne respectivement 47, 6, 20, 26 et 1996.

Pour représenter une expression préfixée en Java, on utilise ici un tableau dont chaque élément représente une entité de l'expression. Ainsi les expressions ci-dessus seront représentées par des tableaux de tailles respectives 1, 5, 5, 13, 29. Les éléments du tableau sont des objets à trois champs, le premier indique la nature de l'entité: (symbole ou nombre), le second champ est rempli par la valeur de l'entité dans le cas où celle ci est un nombre, enfin le dernier champ est un caractère rempli dans les cas où l'entité est un symbole. class Element {
boolean estOperateur;
int valeur;
char valsymb;
}
On utilise les fonctions données ci-dessus pour les piles et on y ajoute les procédures suivantes :

static int calculer (char a, int x, int y) {

switch (a) {
case '+': return x + y;
case '*': return x * y;
}
return -1;
}
La procédure d'évaluation consiste à empiler les résultats intermédiaires, la pile contiendra des opérateurs et des nombres, mais jamais deux nombres consécutivement. On examine successivement les entités de l'expression si l'entité est un opérateur ou si c'est un nombre et que le sommet de la pile est un opérateur, alors on empile cette entité. En revanche, si c'est un nombre et qu'en sommet de pile il y a aussi un nombre, on fait agir l'opérateur qui précède le sommet de pile sur les deux nombres et on répète l'opération sur le résultat trouvé.

static void inserer (Element x, Pile p)
throws ExceptionPile
{
Element y, op;

while (!(Pile.estVide(p) || x.estOperateur ||
Pile.valeur(p).estOperateur)) {
y = Pile.valeur(p);
Pile.supprimer(p);
op = Pile.valeur(p);
Pile.supprimer(p);
x.valeur = calculer (op.valsymb, x.valeur, y.valeur);
}
Pile.ajouter(x,p);
}

static int evaluer (Element u[])
throws ExceptionPile
{
Pile p = new Pile();

for (int i = 0; i < u.length ; ++i) {
inserer (u, p);
}
return Pile.valeur(p).valeur;
}
Dans ce cas, il peut être utile de donner un exemple de programme principal pilotant ces diverses fonctions. Remarquer qu'on se sert des arguments sur la ligne de commande pour séparer les différents nombres ou opérateurs.

public static void main (String args[]) {

Element exp[] = new Element [args.length];

for (int i = 0; i < args.length; ++i) {
String s = args[i];
if (s.equals ("+") || s.equals ("*"))
exp[i] = new Element (true, 0, s.charAt(0));
else
exp[i] = new Element (false, Integer.parseInt(s), ' ');
}
try {
System.out.println (evaluer (exp));
} catch (ExceptionPile x) {
System.err.println ("Pile " + x.nom);
}
}

3.5 Opérations courantes sur les listes

Nous donnons dans ce paragraphe quelques algorithmes de manipulation de listes. Ceux-ci sont utilisés dans les langages où la liste constitue une structure de base. La fonction Tail est une primitive classique, elle supprime le premier élément d'une liste

Figure 3.6 : Queue d'une liste

class Liste {

Object contenu;
Liste suivant;

Liste (Object x, Liste a) {
contenu = x;
suivant = a;
}

static Liste cons (Object x, Liste a) {
return new Liste (x, a);
}

static Object head (Liste a) {
if (a == null)
erreur ("Head d'une liste vide.");
return a.contenu;
}

static Liste tail (Liste a) {
if (a == null)
erreur ("Tail d'une liste vide.");
return a.suivant;
}
Des procédures sur les listes construisent une liste à partir de deux autres, il s'agit de mettre deux listes bout à bout pour en construire une dont la longueur est égale à la somme des longueurs des deux autres. Dans la première procédure append, les deux listes ne sont pas modifiées; dans la seconde nConc, la première liste est transformée pour donner le résultat. Toutefois, on remarquera que, si append copie son premier argument, il partage la fin de liste de son résultat avec son deuxième argument.

Figure 3.7 : Concaténation de deux listes par [i]Append

static Liste append (Liste a, Liste b) {
if (a == null)
return b;
else
return ajouter (a.contenu, append (a.suivant, b)) ;
}

static Liste nConc (Liste a, Liste b) {
if (a == null)
return b;
else {
Liste c = a;
while (c.suivant != null)
c = c.suivant;
c.suivant = b;
return a;
}
}
Cette dernière procédure peut aussi s'écrire récursivement:

static Liste nConc (Liste a, Liste b) {
if (a == null)
return b;
else {
a.suivant = nConc (a.suivant, c);
return a;
}
}

La procédure de calcul de l'image miroir d'une liste a consiste à construire une liste dans laquelle les éléments de a sont rencontrés dans l'ordre inverse de ceux de a. La réalisation de cette procédure est un exercice classique de la programmation sur les listes. On en donne ici deux solutions l'une itérative, l'autre récursive, la complexité est en O(n²) donc quadratique, mais classique. A nouveau, nReverse modifie son argument, alors que Reverse ne le modifie pas et construit une nouvelle liste pour son résultat.

static Liste nReverse (Liste a) {
Liste b = null;
while (a != null) {
Liste c = a.suivant;
a.suivant = b;
b = a;
a = c;
}
return b;
}

static Liste reverse (Liste a) {
if (a == null)
return a;
else
return append (reverse (a.suivant),
ajouter (a.contenu, null));
}
On peut aussi avoir une version linéaire de la version récursive, grâce à une fonction auxiliaire accumulant le résultat dans un de ses arguments: static Liste nReverse (Liste a) {
return nReverse1 (null, a);
}

static Liste nReverse1 (Liste b, Liste a) {
if (a == null)
return b;
else
return nReverse1 (ajouter (a.contenu, b), a.suivant);
}
Un autre exercice formateur consiste à gérer des listes dans lesquelles les éléments sont rangés en ordre croissant. La procédure d'ajout devient plus complexe puisqu'on doit retrouver la position de la cellule où il faut ajouter après avoir parcouru une partie de la liste.

Nous ne traiterons cet exercice que dans le cas des listes circulaires gardées, voir page X. Dans une telle liste, la valeur du champ contenu de la première cellule n'a aucune importance. On peut y mettre le nombre d'éléments de la liste si l'on veut. Le champ suivant de la dernière cellule contient lui l'adresse de la première.

static Liste inserer (int v, Liste a) {

Liste b = a;
while (b.suivant != a && v > head(b.suivant))
b = b.suivant;
b.suivant = ajouter (v, b.suivant);
a.contenu = head(a) + 1;
return a;
}

3.6 Programmes en Caml

/* Déclaration des listes, voir page X */

type element == int;;

type liste = Nil | Cons of cellule

and cellule =
{ mutable contenu : element;
mutable suivant : liste };;
Remarque: en Caml, les listes sont prédéfinies, et la majorité des fonctions suivantes préexistent. Nous nous amusons donc à les redéfinir. Toutefois, nos nouvelles listes sont modifiables.


(* Liste vide, voir page X *)
let estVide a =
a = Nil;;

(* Ajouter, voir page X *)
let ajouter x a =
Cons {contenu = x; suivant = a};;
(* Recherche, voir page X *)
let recherche x a =
let l = ref a in
let result = ref false in
while !l <> Nil do
match !l with
| Cons {contenu = y; suivant = s} ->
if x = y then result := true
else l := s
| _ -> ()
done;
!result;;
(* Recherche récursive, voir page X *)
let recherche x a =
match a with
Nil -> false
| Cons {contenu = y; suivant = s} ->
if x = y then true
else recherche x s;;
let recherche x a =
match a with
Nil -> false
| Cons {contenu = y; suivant = s} ->
x = y || recherche x s;;