Suppression/Insertion d’un maillon de liste

Prototype

Généralités

Intuitivement, une pile correspond à une pile de livres sur une table. La première opératoin consiste à poser un livre sur la table vide. L’opération suivante place un second livre sur le livre déjà posé sur la table. Chaque opération de rangement augmente la taille de la pile. Prendre un livre sans provoquer l’effondrement de la pile n’est possible qu’au sommet de la pile.

Traitement des expressions

En mode infixé, écrire une expression consiste à :

écrire un opérateur entre 2 opérandes,
écrire un opérateur unaire suivit de son opérande,
modifier l’ordre des priorités à l’aide de parenthèses.

Le traitement informatique d’une expression prefixée est malaisé. Il est préférable d’effectuer le traitement de l’expression équivalente en mode postfixé ou infixé. Par exemple, l’expression $(3 + 4)\times 2$ devient $3 \; 4 + 2 \times$ en notation postfixée.

$\begin{tabular}{c|l|l} \hline \hline Symboles & Pile & Actions \\ \hline 3 & 3 & {\it push} 3 \\ 4 & 3, 4 & {\it push} 4 \\ + & & {\it pop} 4 ; {\it pop} 3 \\ & & calculer $7 = 3 + 4 $ \\ & 7 & {\it push} 7 \\ 2 & 7, 2 & {\it push} 2 \\ $\times$ & & {\it pop} 2 ; {\it pop} 7 \\ & & calculer $14 = 7 \times 2 $ \\ & 14 & {\it push} 14 \\ \hline \end{tabular}$

Règles de transformation

Les variables successivement rencontrées dans l’expression infixée sont rangées directement dans l’expression préfixée.
Les opérateurs sont emplilés en tenant compte de leur priorité :
- priorité de l’opérateur ds l’expression $>$ priorité de l’opérateur au sommet de la pile $\Longrightarrow$ empiler l’opérateur,
- priorité de l’opérateur ds l’expression $<=$ priorité de l’opérateur au sommet de la pile $\Longrightarrow$ désempiler et ranger l’opérateur désemplilé dans l’expression postfixée.
Empiler systématiquement une parenthèse ouvrante car elle délimite une sous-expression,
la parenthèse fermante fait sortir tous les éléments de la pile jusqu’à la rencontre d’une parenthèse ouvrante.

Écriture au moyen d’un type de données abstrait

struct item
{           
   int type ;
   union   {    
       char op  ; int  val ;
   } contenu ;
    
} ;         
typedef struct item   ITEM ;
typedef struct item * Item ;
...
pile (Item) ; Itempile p ; 

int ValLex ; int Symbole ;
...
Emettre (int Lex, int Val)
{
     ITEM x ; Item y ;

     switch (Lex)
     {
     case '+' : case '-' : case '*' : case '/' :
            x.type = OP  ;
         x.contenu = Lex ;
         y = Item_copier(&x) ;
         Itempile_empiler  (p, y) ;
         break ;

     case NB :  /* C'est un nombre */
             x.type = NB ;
         x.contenu = Val ;
         y = Item_copier(&x) ;
         Itempile_empiler  (p, y) ;
         break ;

     default :
     }
}

main ()
{
    p = Itempile_creer(Item_copier,
            Item_detruire, Item_editer) ;

    Analyse() ;
}

Suppression/Insertion d’un maillon de liste