View
106
Download
0
Category
Preview:
Citation preview
Structures de donnéesIFT-10541
Abder AlikacemAbder Alikacem
Les piles
Département d’informatique et de génie logiciel
Édition Septembre 2009
! +
Plan
• Introduction et exemples d’application• Description en terme de type abstrait• Implantation
Piles
Piles :
LIFO : last in, first outDAPS : dernier arrivé, premier sorti
ex. : assiettes
livresfacturespile d’exécutionévaluation d’expressions
in out
pile
Files
Files :
FIFO : first in, first outPAPS : premier arrivé, premier sorti
ex. : assiettesfacturesbanquechaîne de montageimprimantetâches à exécuter
out in
file
Piles et files
Structures de données auxiliaires• car utilisées par d’autres structures
(comme les listes ordonnées)
Utilité :• support à des applications• support à d’autres structures de données• modélisation de la réalité• en informatique : système d’exploitation
gestion interne évaluation d ’expressions etc.
Piles
Spécification Une pile est une structure de données abstraite contenant des éléments
homogènes (de type non précisé) à 1 point d’accès et permettantd’ajouter une valeur à la pile (empiler ou push);de lire la dernière valeur ajoutée ;d’enlever la dernière valeur ajoutée (dépiler ou pop);de tester si la pile est vide.
On ne « connait » donc de la pile que le dernier élément empilé (sonsommet).
Spécification physique liste chaînéeoutableau statique ou dynamique
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
in
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
out
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
out
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• consulter le premier élément de la pile
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• consulter le premier élément de la pile
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
• vérifier si un élément est sur la pile
pile
?
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
• vérifier si un élément est sur la pile
pile
?
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
• vérifier si un élément est sur la pile
pile
?
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
• vérifier si un élément est sur la pile
pile
?
!
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
• regarder si un élément est sur la pile
• remplacer un élément sur la pile
pile
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
• regarder si un élément est sur la pile
• remplacer un élément sur la pile
pile
Piles
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
• regarder si un élément est sur la pile
• remplacer un élément sur la pile
les noms anglais pour ces opération sont: PUSH—EMPILER, POP—DÉPILER, TOP—SOMMET, PEEP—EXAMINER et CHANGE—CHANGER.
pile
Piles
Préoccupation de la programmation par objet
initialiser une pile (constructeurs); détruire une pile de ses éléments (destructeur); Constructeur de copie; Surcharge de l’opérateur =
Piles
pile
Vue externe
La pile est une structure monolithique, c.-à-d. qu'une pile n'est pas construite à l'aide de sous-piles. Pour cette raison les opérations de Mise à jour ne vont pas créer de nouvel objet Pile mais uniquement modifier l'état de la pile qui reçoit le message.
Piles
Pile = liste + gestion adaptée
manipulations (empiler et dépiler) par le même point d’accès
in
out
pile pile
out
in
• empiler (push) :
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
• sommet (top) :
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
• sommet (top) :• L1 (ou : L|L|)
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
• sommet (top) :• L1 (ou : L|L|)
• pile vide ?
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
• sommet (top) :• L1 (ou : L|L|)
• pile vide ?• L = ?
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
• sommet (top) :• L1 (ou : L|L|)
• pile vide ?• L = ?
• élément sur la pile (peep) ?
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
• sommet (top) :• L1 (ou : L|L|)
• pile vide ?• L = ?
• élément sur la pile (peep) ?• x L?
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
• sommet (top) :• L1 (ou : L|L|)
• pile vide ?• L = ?
• élément sur la pile (peep) ?• x L?
• remplacer un élément sur la pile
Pile = liste + gestion adaptée
• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)
• dépiler (pop) :• L -1L (ou : L -|L|L)
• sommet (top) :• L1 (ou : L|L|)
• pile vide ?• L = ?
• élément sur la pile (peep) ?• x L?
• remplacer un élément sur la pile• x = L?; L -?L; L L +? y
Pile = liste + gestion adaptée
Piles : spécifications de l’interface
empiler : p p + x• prototype :
void empiler(TypeEl x);
/** * \brief Empiler un élément dans la pile * * \pre Il y a assez de mémoire pour empiler x * * \post La pile comprend un élément de plus * \post La pile est inchangée sinon * * \exception bad_alloc si pas assez de mémoire * */
dépiler : -p • prototype :
void depiler();/**
* \brief Dépiler la pile * * \pre La pile a au moins un élément * * \post La pile comprend un élément de moins * \post La pile est inchangée sinon * * \exception logic_error si la pile est vide * */
Piles : spécifications de l’interface
sommet : !p • prototype :
TypeEl sommet();/**
* \brief Consulter le sommet de la pile * * \pre La pile a au moins un élément * * \post La pile est inchangée * \post Une copie de l’élément au sommet est retournée
* * \exception logic_error si la pile est vide * */
Piles : spécifications de l’interface
pile vide : p = ?• prototype :
bool estVide();/**
* \brief Vérifier si la pile est vide * * \post La pile est inchangée * \post VRAI ou FAUX est retourné selon que la pile est vide ou non * */
Piles : spécifications de l’interface
appartenance : x p?• prototype :
bool appartient(TypeEl x);/**
* \brief Vérifier si un élément appartient à la pile * * \post La pile est inchangée * \post VRAI ou FAUX est retourné selon que x à la pile ou non *
*/
Piles : spécifications de l’interface
remplacement : p p - x/y• prototype :
void remplacer(TypeEl x, TypeEl y);
/** * \brief Remplacer un élément dans la pile* * \pre x appartient à la pile**\post Le premier x trouvé (en débutant au sommet) est remplacé par
y*\post La pile est inchangée sinon* *\exception logic_error si pas dans la pile * */
Piles : spécifications de l’interface
La classe Piletemplate <typename T>class Pile{private:
//...Modèle d’implantationpublic:
// constructeurs et destructeursPile(); //constructeurPile(const Pile&) throw(bad_alloc); //constructeur copie~Pile(); //destructeur
// Modificateursvoid empiler(T) throw (bad_alloc);T depiler()throw(logic_error);
//Sélecteursbool estVide(){ return sommet == 0;}int taille() { return cpt;}T& sommet() throw (logic_error); // élément au sommet
//surcharge d'opérateursPile<T>& operator = (const Pile<T>&) throw
(bad_alloc);friend ostream& operator << (ostream& , const Pile& );
};
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès : indice 0)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
• en tableau : (accès par la fin)
0 1 2 3 4 ... 99
pile
Piles : modèles d’implantation
Piles : implantation dans un tableau
Implantation dans un tableau dynamique
{ private :
T* tab; int sommet; int tailleMax;
public: …
Tableau tab réservé dans le tas
Constructeur avec un paramètre : taille maximum
==> bonne implantation si on peut évaluer la taille maximum à l’utilisation de la pile
Piles : implantation dans un tableau
template <typename T, in MAX = 100 >class Pile {private :
T* tab; int sommet; int tailleMax;
public:Pile(const int max = MAX) throw (bad_alloc);// constructeur : init taille maxi... ~Pile (void); // destructeur
};
Implantation dans un tableau dynamique
Piles : implantation dans un tableau
template <Typename T>Pile<T> :: Pile (int max) throw (bad_alloc){
tab = new T [max];sommet = -1;maxTaille =max;
}
template <class T>Pile<T> :: ~Pile (void) { if (tab!=0) delete [ ] tab;}
Constructeur
Destructeur
Piles : implantation dans un tableau
template <typename T>T Pile<T> :: depiler(void) throw (logic_error){
if (!estVide()) return tab[sommet--];else
throw logic_error("Depiler: la pile est vide!");}
template <typename T>bool Pile<T> :: estVide (void){
return (sommet == -1);}
dépiler
Sélecteur : vide
Piles : implantation dans un tableautemplate <typename T>void Pile<T> :: empiler(const T& e) throw (length_error){
if (sommet+1 < maxTaille) { sommet += 1;
tab[sommet] = e; }else{
throw length_error("Empiler:la pile est pleine\n");
}
empiler
Remarque : on suppose que l ’opérateur d ’affectation existe ou est surchargé dans la classe qui correspond au paramètre T.
=> intérêt de la surcharge des opérateurs
Piles : implantation dans un tableau
Remarque
Il faut cependant noter que la contrainte de pile pleine n’est pas une contrainte liée à la structure de donnée pile. Théoriquement, il n’y a pas de limite sur le nombre d’éléments d’une pile. En pratique, son implantation dans un tableau limite le nombre d’éléments à maxTaille.
Piles : implantation dans un tableau
template <typename T>Pile<T>& Pile<T> :: operator = (const Pile<T>& p) {
if (tab!=0) delete [ ] tab; //on nettoie thistab=new T [p.maxTaille];
maxTaille=p.maxTaille;for (int i=0; i<maxTaille;i+=1)
tab[i]=p.tab[i];sommet=p.pommet;
return (*this);//retourner : une référence sur l ’objet courant}
Surcharge de l’op. =
Piles : implantation dans un tableau
template <typename T>Pile<T> :: Pile (const Pile<T>& p) { tab=new X [p.maxtaille];
maxTaille=p.maxTaille;for (int i=0; i<maxTaille;i+=1)
tab[i]=p.tab[i];sommet=p.sommet;
}
Constructeur de copie
• liste chaînée
debut
pile
Piles : modèles d’implantation
• liste chaînée : empiler
debut el
suivant
pile
Piles : modèles d’implantation
• liste chaînée : empiler
debut el
suivant
el
suivant
pile
Piles : modèles d’implantation
• liste chaînée : empiler
debut el
suivant
el
suivant
pile
Piles : modèles d’implantation
• liste chaînée : empiler
debut el
suivant
el
suivant
el
suivant
pile
Piles : modèles d’implantation
• liste chaînée : empiler
debut el
suivant
el
suivant
el
suivant
pile
Piles : modèles d’implantation
• liste chaînée : dépiler
debut el
suivant
el
suivant
el
suivant
pile
Piles : modèles d’implantation
• liste chaînée : dépiler
debut el
suivant
el
suivant
el
suivant
pile
x
Piles : modèles d’implantation
• liste chaînée : dépiler
debut el
suivant
el
suivant
pile
Piles : modèles d’implantation
• liste chaînée : dépiler
debut el
suivant
el
suivant
pile
x
Piles : modèles d’implantation
• liste chaînée : dépiler
debut el
suivant
pile
Piles : modèles d’implantation
• liste chaînée : dépiler
debut el
suivant
pile
x
Piles : modèles d’implantation
• liste chaînée : dépiler
debut
pile
Piles : modèles d’implantation
Piles : implantation dans une liste chaînée
template <typename T>class Noeud{public:
Noeud (const T& data_item, Noeud * next_ptr = 0) :el(data_item), suivant(next_ptr) {}//constructeur
~Noeud () {}; //destructeur qui ne fait rien
};
friend class Pile <T>;
private :T el;Noeud<T> * suivant;
Version 1Implantation dans une liste chaînée
Piles : implantation dans une liste chaînée
template <typename T>class Pile {public: Pile (); // Constructeur Pile (const pile<X>&) throw (bad_alloc); // Constructeur par
copie ~Pile (); // Destructeur
Pile<T>& operator=(const Pile<T>& P); // P1 = Pvoid empiler (const T& a) throw (bad_alloc); T depiler () throw (logic_error);
T& sommet (void) throw (logic_error); // sélecteur : valeur //placée au sommet
bool vide(); //sélecteur : ( IC est vide?)
};
private :Noeud<T>* sommet; // pointeur sur la cellule sommetint cpt; // Nombre d'élements de la pile void detruire (); //Méthode privée utile pour le destructeur
// et l’op. =
Version 1
Piles : implantation dans une liste chaînée
template <typename T>class Pile {public:
Pile (); Pile (const Pile<T>&) throw (bad_alloc); ~Pile (); Pile<T>& operator=(const Pile<T>& P); //..
private:class Noeud{public: T el;
Noeud * suivant;Noeud (const T& data_item, Noeud * next_ptr = 0) :el(data_item), suivant(next_ptr) {}
};typedef Noeud * elem;elem sommet;int cpt; void detruire ();
};
Version 2
Piles : implantation dans une liste chaînée
template <typename T>Pile<T>::Pile (void){ sommet =0; cpt = 0;}
template <class X>Pile<X>:: ~Pile(void){ if (sommet != 0) detruire( );}
template <typename T>void Pile<T>::detruire () {
Noeud<T>* p;while (sommet != 0){
p=sommet->suivant;delete sommet;sommet=p;
}}
constructeur
destructeur
Piles : implantation dans une liste chaînée
template <typename T>void Pile<T>::detruire () {
…delete (sommet);
}
template <typename T>Noeud<T>:: ~Noeud (void){ if (sommet!=0) delete sommet;}
Pour que l ’espace occupé par les composants pointés dans chaque nœud soit libéré lorsque la fonction détruire est appliquée, autre version, il faut un destructeur de noeud qui ait cet effet :
Chaque fois que l’instruction delete est appliquée sur un pointeur de cellule, alors le destructeur de la classe Noeud est activé.
Libère l ’espace occupé par le composant pointé par ptr
Autre version
Les piles
Comparaison des 2 implantations Toutes les implantations des opérations d’une pile utilisant un tableau
ou une liste chaînée prennent un temps constant i.e. en O(1). Par conséquent, d’un point de vue d’efficacité, aucune des deux implantations n’est mieux que l’autre. D’un point de vue de complexité spatiale, le tableau doit déclarer une taille fixe initialement. Une partie de cet espace est perdue quand la pile n’est pas bien remplie. La liste peut augmenter ou rapetisser au besoin mais demande un extra espace pour mémoriser les adresses des pointeurs.
Exemples d’utilisation des piles
Le problème des parenthèses : étant donnée une expression avec desparenthèses, est-elle bien ou mal parenthésée ?
((a + b) c − (d + 4) (5 + (a + c))) (c + (d + (e + 5 g) f) a)(correct)
(a + b)((incorrect)
Encore un peu plus complexe : différentes parenthèses. Exemple avec [ et (([])[()(()[])] : correct([)] : incorrect
Vérification de parenthèsage
Tant que lire caractère cSi c est ( ou [
empiler cSinon
Si c est ) ou ]Si pile vide
ÉCHECSinon
c′ = lire la pileSi c et c′ correspondent
dépilerSinon
ÉCHECSi pile vide
OKSinon
ÉCHEC
Code C++
bool check(string s) {Pile p;for (unsigned int i(0); i < s.size(); ++i) {
if ((s[i] == ’(’) || (s[i] == ’[’))p.empile(s[i]);else if (s[i] == ’)’) {
if ((!p.est_vide()) && (p.top() == ’(’))p.depile();
elsereturn false;
} else if (s[i] == ’]’) {if ((!p.est_vide()) && (p.top() == ’[’))
p.depile();else
return false;}
}return p.est_vide();}
Exemples d’application des piles
Reconnaissance syntaxique : Soit une chaîne de caractères définie par
la règle suivante : Une chaîne quelconque S suivie du caractère *, suivi de la chaîne S inversée.
Exemple abc*cba La chaîne peut contenir n’importe quel caractère alphanumérique. La
chaîne se termine par le marqueur fin de ligne.
Conception : Pour déterminer si la chaîne est légale, il faut :1) Lire jusqu’à ‘*’ les caractère un à un en les empilant dans une pile.2) Après ‘*’, jusqu’à la fin de la chaîne, lire un caractère, dépiler le
caractère au sommet de la pile et comparer les deux, s’il ne sont pas égaux, la chaîne est invalide.
3) Si tous les caractères sont égaux et que la pile s’est vidée, la chaîne est valide.
Exemples d’application des piles
Calcul arithmétique : Une application courante des piles se fait dans le
calcul arithmétique: l'ordre dans la pile permet d'éviter l'usage des parenthèses. La notation postfixée (polonaise) consiste à placer les opérandes devant l'opérateur. La notation infixée (parenthèsée) consiste à entourer les opérateurs par leurs opérandes. Les parenthèses sont nécessaires uniquement en notation infixée. Certaines règles permettent d'en réduire le nombre (priorité de la multiplication par rapport à l'addition, en cas d'opérations unaires représentées par un caractère spécial (-, !,...). Les notations préfixée et postfixée sont d'un emploi plus facile puisqu'on sait immédiatement combien d'opérandes il faut rechercher.
Exemples d’application des piles
Calcul arithmétique : Détaillons ici la saisie et l'évaluation d'une
expression
Postfixée. La notation usuelle, comme (3 + 5) * 2, est dite infixée. Son défaut est de nécessiter l'utilisation de parenthèses pour éviter toute ambiguïté (ici, avec 3 + (5 * 2)). Pour éviter le parenthésage, il est possible de transformer une expression infixée en une expression postfixée en faisant "glisser« les opérateurs arithmétiques à la suite des expressions auxquelles ils s'appliquent.
Exemple
(3 + 5) * 2 s'écrira en notation postfixée (notation polonaise): 3 5 + 2 *alors que 3 + (5 * 2) s'écrira: 3 5 2 * +
Calcul arithmétique: On voit que la multiplication vient immédiatement
après ses deux opérandes A et B. Imaginons maintenant que A * B est calculé et stocké dans T. Alors la division / vient juste après les deux arguments T et C.
Forme infixe: A/B ** C + D * E - A * CForme postfixe: ABC ** /DE * + AC * -
Exemples d’application des piles
Evaluation en Postfixe
Considérons l’expression en postfixe suivante: 6 5 2 3 + 8 * + 3 + *
AlgorithmeInitialiser la pile à vide;while (ce n’st pas la fin del’expression postfixée) {
prendre l’item prochain de postfixe;if(item est une valeur)empiler;else if(item operateur binaire ) {
dépiler dans x;dépiler dans y;effectuer y operateur x;empiler le résultat obtenu;
} else if (item opérateur unaire) {dépiler dans x;effectuer opérateur(x);empiler le résultat obtenu;}
}
la seule valeur qui reste dans la pile est le résultat recherché.
Opérateur binaires: +, -, *, /, etc.,
Opérateur unaires: moins unaire, racine carrée, sin, cos, exp, … etc.
Exemples d’application des piles
Exemples d’application des piles
Infixe à Postfixe
Algorithmeinitialise la pile et l’output postfixe à vide;while(ce n’est pas la fin de l’expression infixe) {
prendre le prochain item infixeif (item est une valeur) concaténer item à postfixeelse if (item == ‘(‘) empiler itemelse if (item == ‘)’) {
dépiler sur xwhile(x != ‘(‘)concaténer x à postfixe & dépiler sur x
}else {while(precedence(stack top) >= precedence(item))dépiler sur x et concaténer x à postfixe;empiler item;}
}while (pile non vide)dépiler sur x et concaténer x à postfixe;
Bien entendu la notation postfixe ne sera pas d’une grande utilité s’il n’existait pas unalgorithme simple pour convertir une expressioninfixe en une expression postfixe.
Encore une fois, cet algorithme utilise une pile.
Exemples d’application des piles
Infixe à Postfixe
Algorithmeinitialise la pile et l’output postfixe à vide;while(ce n’est pas la fin de l’expression infixe) {
prendre le prochain item infixeif (item est une valeur) concaténer item à postfixeelse if (item == ‘(‘) empiler itemelse if (item == ‘)’) {
dépiler sur xwhile(x != ‘(‘)concaténer x à postfixe & dépiler sur x
}else {while(precedence(stack top) >= precedence(item))dépiler sur x et concaténer x à postfixe;empiler item;}
}while (pile non vide)dépiler sur x et concaténer x à postfixe;
Précédence des opérateurs4 : ‘(‘ – déplée seulement si une ‘)’ est trouvée3 : tous les opérateurs unaires2 : / *1 : + -
L’algorithme passe les opérandes à la forme postfixe, mais sauvegarde les opérateurs dans la pile jusqu’à ce que tous les opérandes soient tous traduits.
Recommended