Cours 11 du 6 avril :
Utilisation des piles:
expressions arithmétiques
Expression arithmétiques formées à partir d'opérateurs binaires
· forme préfixe: + a b.
o On peut donner une définition récursive de ce qu'est une expression préfixe:
§ une expression préfixe est soit un nombre (a) soit un opérateur suivi d'une première expression préfixe suivie d'une deuxième expression préfixe (+ a b)
· ExpressionPréfixe = opérateur ExpressionPréfixe ExpressionPréfixe
· Expressionprefixe = nombre
· forme infixe : (a + b) (avec parenthèses)
· ExpressionInfixe = ( Expressioninfixe opérateur ExpressionInfixe )
· ExpressioInfixe = nombre
· forme postfixe: + a b
· ExpressionInfixe = Expressioninfixe opérateur ExpressionInfixe opérateur
· ExpressioInfixe = nombre
Exemples:
Une expression peut être représentée par un arbre:
qui correspond à
· l'expression préfixe: + * a b * + a b c
· l'expression infixe parenthèsée ((a * b) + ((a+b)* c))
· l'expression postfixe : a b * a b + c* +
On obtient ces expressions à partir de l'arbre par un parcours (récursif) à partir de la racine:
- AfficherPrefixe pour la forme préfixe:
- pour une feuille afficher la feuille
- sinon afficher le nœud puis AfficherPrefixe pour le sous arbre gauche puis AfficherPrefixe pour le sous arbre droit
- AfficherInfixe pour la forme infixe:
- pour une feuille afficher la feuille
- sinon
afficher '(' puis AfficherPrefixe
pour le sous arbre gauche puis afficher le nœud puis AfficherPrefixe pour
le sous arbre droit puis afficher ')'
- AfficherPostfixe pour la forme postfixe:
- pour une feuille afficher la feuille
- AfficherPrefixe pour le sous arbre gauche puis AfficherPrefixe pour le sous arbre droit puis afficher le nœud.
On peut noter qu'il n'y a pas d'ambiguïté pour les expressions préfixes et postfixes : à + * a b * + a b c ou à a b * a b + c* + ne correspond qu'un seul arbre, ce n'est pas la même chose pour une expression infixe si l'on supprime les parenthèses, à a*b+a+b*c correspond (par exemple) aussi à l'arbre:
qui correspond à l'expression ((((a*b)+a)+b)*c)
Expressions sous forme postfixe:
On peut déterminer qu'une expression est bien une expression postfixe avec un compteur de la manière suivante:
- le compteur est initialisé à 0
- en lisant l'expression de gauche à droite on incrémente le compteur à chaque fois qu'on rencontre un nombre et on décrémente le compteur si on rencontre un opérateur
il s'agit d'une expression postfixe si et seulement si le compteur est toujours positif et sa valeur finale est égale à 1.
Exemple:
a b * a b + c *
+
0 1 2 1 2 3 2 3 2 1
Evaluation d'espressions
sous forme postfixe
On peut aussi évaluer simplement l'expression sous forme postfixe avec une pile:
- quand on lit un nombre on l'empile,
- quand on lit un opérateur op , on dépile pour obtenir le deuxième argument b, on dépile pour obtenir le premier argument a et on empile le résultat de op(a,b)
Exemple supposons que a=12, b=2 et c=4, on obtiendra successivement sur la pile:
2 4
2
12 12 14 14 56
12 12 24 24 24 24 24
24 80
* + * +
Considérons une classe de Pile pour contenir des entiers:
// Pile de Integer
// attention aux conversions automatiques entre Integer et int
class PileInt {
private PileListe p;
public PileInt(){p=new
PileListe();}
public PileInt(int
n){this();};
public void
empiler(int i){
p.empiler(i);
}
public int depiler(){
return
(Integer)(p.depiler());
}
}
On notera que pour utiliser
Remarques:
- il y a de nombreuses conversions implicites: exemple p.empiler(i)… l'entier i est converti en un objet Integer
- il y a une conversion explicite du résultat de p.depiler qui est un Object en Integer suivi d'une conversion implicite de cet Integer en int.
- PileInt n'implémente pas Pile mais utilise une PileListe
public static int evalPost(String st) {
char[] a = st.toCharArray();
int N = a.length;
PileInt s = new PileInt(N);
for (int i = 0; i < N; i++) {
if (a[i]=='
')continue;
if (a[i] == '+')
s.empiler(s.depiler() + s.depiler());
if (a[i] == '*')
s.empiler(s.depiler() *
s.depiler());
if ((a[i] >= '0') &&
(a[i] <= '9')){
s.empiler(0);
while((a[i] >= '0')
&& (a[i] <= '9')&& (i<N))
s.empiler(10*s.depiler() +
(a[i++]-'0'));
i--;
}
}
return s.depiler();
}
Remarques:
- noter la conversion toCharArray()qui permet de passer d'une chaîne de caractères à un tableau de caractères.
- la conversion en entier se fait aussi en utilisant la pile.
Évaluation d'une expression préfixe
Pour évaluer récursivement une expression préfixe, le
principe est assez simple. rappelons qu'une expression sous forme préfixe est
de la forme opérateur expression
expression ou nombre.
- Si l'expression e est de la forme opérateur expression1 expression2, eval(e)=opérateur(eval(expression1),eval(expression2)
- Si
l'expression e est un nombre n eval(e)=n
// evaluation récursive d une expresssion
simple
// sous forme préfixe
contenue dans in
static String in; //
la chaîne à évaluer
static int
i=0;
static int evalPre(){
while (in.charAt(i)==' ')i++;
if(in.charAt(i)=='+'){
i++;
return evalPre()+evalPre();
}
if(in.charAt(i)=='*'){
i++;
return evalPre()*evalPre();
}
int x=0;
while(i<in.length() &&
(in.charAt(i)>='0') && (in.charAt(i)<='9')){
x=10*x+(in.charAt(i)-'0');
i++;
}
return x;
}
}
Conversions
On peut sur le même préfixe convertir une expression sous forme préfixe en une expression parenthèsée sous forme infixe: au lieu de calculer le résultat on écrit sur la pile le résultat la chaîne de caractères.
// conversion de
Postfixe vers Infixe avec une PileTable
public
static String Post2Inf(String arg){
char[]
a = arg.toCharArray();
int N = a.length;
String tmp="";
Pile s = new PileTable(N);
for (int i = 0; i < N; i++) {
if (a[i]=='
')continue;
if ((a[i] == '+')||(a[i] == '*')){
tmp=(String)s.depiler();
s.empiler("("+s.depiler()
+a[i]+ tmp+")");
}
if ((a[i] >= '0') &&
(a[i] <= '9')) {
tmp="";
while((a[i] >= '0')
&& (a[i] <= '9')&& (i<N))
tmp += a[i++];
s.empiler(tmp);
}
}
return (String) s.depiler();
}
pour la conversion depuis une expression sous forme infixe avec parenthèses à une expression sous forme postfixe on peut aussi utiliser une pile: on empile les opérateurs, on écrit directement les nombres et on dépile quand on rencontre une parenthèse fermante:
//
conversion de Infixe à Postfixe
public static String Inf2Post(String args)
{
char[] a = args.toCharArray();
int N = a.length;
Pile s = new PileTable(N);
String res="";
for (int i = 0; i < N; i++) {
if (a[i] == ')')
res = res + s.depiler()+"
";
if (a[i] == '(') continue;
if(a[i]==' ')continue;
if ((a[i] == '+') || (a[i] == '*'))
s.empiler(a[i]);
if((a[i] >= '0') &&
(a[i] <= '9')){
while ((a[i] >= '0')
&& (a[i] <= '9'))
res =res+a[i++];
i--;
res=res+" ";
}
}
return res;
}