Corrigé 27.  Enoncé

1. Implémentation d'une liste linéaire chaînée de piles

Liste en dynamique, Pile en statique

    TYPE Typelist = POINTEUR( Tmaillon);
    TYPE Tmaillon = STRUCTURE
        Val    : Typepile
        Suiv    : POINTEUR(Tmaillon)
    FIN
    TYPE Typepile = STRUCTURE
        Tab     : TABLEAU[1..N] DE Typeqq
        Som    : ENTIER
    FIN

Liste en dynamique, Pile en dynamique

    TYPE Typelist = POINTEUR( Tmaillon);
    TYPE Tmaillon = STRUCTURE
        Val    : Typepile
        Suiv    : POINTEUR(Tmaillon)
    FIN
    TYPE Typepile = POINTEUR( Tmaillon1)
    TYPE Tmaillon1 = STRUCTURE
        Val    : Typeqq
        Suiv    : POINTEUR(Tmaillon1)
    FIN

Liste en statique, Pile en dynamique

    { 1 est l'adresse du premier élément de la liste dans le tableau }
    TYPE Typeliste = TABLEAU[1..M] DE Typeelementtableau
    TYPE Typeelementtableau = STRUCTURE
        Val    : Typepile
        Suiv    : ENTIER
        Vide    : BOOLEEN
    FIN
    TYPE Typepile = POINTEUR( Tmaillon1)

    TYPE Tmaillon1 = STRUCTURE
        Val    : Typeqq
        Suiv    : POINTEUR(Tmaillon1)
    FIN

Liste en statique, Pile en statique

    TYPE Typeliste = TABLEAU[1..M] DE Typeelementtableau
    TYPE Typeelementtableau = STRUCTURE
        Val    : Typepile
        Suiv    : ENTIER
        Vide    : BOOLEEN
    FIN
    TYPE Typepile = STRUCTURE
        Tab     : TABLEAU[1..N] DE Typeqq
        Som    : ENTIER
    FIN

2. Traduction automatique d'une procédure récursive

Traduction automatique

La Zdd contient les champs X, Y et Adr. Adr étant l'adresse de retour.

        Lire(N, M)
        Creerpile(P)
        Empiler(P, Zdd)
        {Préparation Premier Appel}
        Zdd.X := N
        Zdd.Y := M
        Zdd.Adr := 1
10    SI Zdd.Y = 0
            R := 0
            {Retour}
            I := Zdd.Adr
            Depiler(P, Zdd)
            Allera I
        FSI
        {Appel}
        Empiler(P, Zdd)
        Zdd.X := Zdd.X * 2
        Zdd.Y := Zdd.Y DIV 2
        Zdd.Adr := 2
        Allera 10

2     SI NON Pair(Zdd.Y) : R := R + Zdd.X FSI
      {Retour}
      I := Zdd.Adr
      Depiler(P, Zdd)
      Allera I
1    Ecrire( R)
   
Trace

Les différents états de la pile sont : (x, x, x) --> (5, 5, 1) --> (10, 2, 2) --> (20, 1, 2)
Les différentes valeurs de la zone de données : (5, 5, 1); (10, 2, 2); (20, 1, 2); (40, 0, 2); (20,1, 2); (10,2, 2); (5, 5, 1).

Algorithme amélioré

Il suffit d'éliminer l'adresse de retour de la zone de données comme elle est unique. On remplace alors l'opération Dépiler(Pile, Zdd) par Dépiler(Pile, Zdd, Possible). Ainsi, quand un dépilement n'est plus possible, il y a retour vers l'appelant.

        Lire(N, M)
        Creerpile(P)
        {Préparation du premier appel}
        Zdd.X := N
        Zdd.Y := M
10    SI Zdd.Y = 0
            R := 0
            {Retour}
            Dépiler(P, Zdd, Possible)
            SI Possible : Allera 2 SINON Allera 1 FSI
            {Appel}
            Empiler(P, Zdd)
            Zdd.X := Zdd.X * 2
            Zdd.Y := Zdd.Y DIV 2
            Allera 10
2    SI NON Pair(Zdd.Y) : R := R + Zdd.X FSI
      {Retour}
      Dépiler(P, Zdd, Possible)
      SI Possible : Allera 2 SINON Allera 1 FSI
1    Ecrire( R)       

3. Evaluation d'une expression arithmétique préfixée

Soient :
- Pileoper la pile des opérateurs ,
- Pileval la pile des résultats intermédiaires,
- V1 et V2 des variables réelles
- C une variable caractère
et soient :
- Nb(Pileoper) le nombre de '!' au sommet de la pile PileOper représentant le nombre d'opérandes.
- Operation( Op, V1, V2) le module qui effectue l'opération Op entre V1 et V2.

On suppose que toutes les opérations sont binaires.

L'algorithme d'évaluation est le suivant :

    Creerpile( Pileoper )
    Creerpile( Pileval )
    FIN := FAUX
    TANTQUE NON FIN
        Remplir
        Evaluer
    FINTANTQUE

Avec les modules Remplir et Evaluer définis comme suit :

Remplir :   

    Lire( C)
    { On suppose que la chaîne de caractères se termine par le caractère "#" }
    TANTQUE ( Nb(Pileoper) < 2 ET C <> '#' ) :
        SI Operateur(C) :
            Empiler( Pileoper, C)
        SINON
            Empiler(Pileval, Val(C) )
            Empiler(Pileoper, '!' )
        FSI
        Lire( C)
    FINTANTQUE
    FIN := ( C = '#' )

Evaluer :

    TANTQUE ( Nb(Pileoper) = 2 ) :
        Dépiler ( Pileoper, Op) ; Dépiler(Pileval, V1);
        Dépiler ( Pileoper, Op) ; Dépiler(Pileval, V2);
        Dépiler (Pileoper, Op)
    Empiler (Pileval, Operation( Op, V1, V2) )
    Empiler (Pileoper, '!')
    FINTANTQUE