Corrigé 18.  Enoncé

1. Expression arithmétique sous forme d'un arbre binaire

Exemple

Algorithme récursif d'évaluation

Nous utilisons le prédicat Operande(T), égal à VRAI si Info(T) est un opérande, égal à FAUX sinon.

Remarque :
- Opérande(T) peut être implémenté comme un champ additionnel.
- le champ Info est donc sous forme canonique.

Soit A un arbre représentant une expression arithmétique. L'algorithme d'évaluation est le suivant :

    Eval(A) :

    SI Operande(A) :
        Eval := Info(A)
    SINON
        Eval := Oper(Info(A), Eval(Fg(A), Eval(Fd(A))
    FSI

Avec Oper une fonction qui effectue l'opération mentionnée par Info(A) entre deux valeurs Eval(fg(A)) et Eval(fd(A)).


2. Expression arithmétique sous forme polonaise postfixée

Exemple

(a + b) * (c - d) est représentée comme : a b + c d - *

Algorithme

Nous supposons que chaque caractère est soit un identificateur d'une variable, soit un opérateur, soit un caractère quelconque.

Nous utilisons les prédicats suivants :

Operande(C)    : égal à VRAI si C est un opérande, FAUX sinon.
Binaire(C)    : égal à VRAI si C est un opérateur binaire, FAUX sinon.
Unaire(C)     : égal à VRAI si C est un opérateur unaire, FAUX sinon

et les fonctions :

Val(C) : attribue la valeur associée à C (nous supposons par exemple qu'il existe une table de correspondante variable <---> valeur ).
Oper1     : effectue l'opération binaire mentionnée par C entre deux valeurs V1 et V2.
Oper    : effectue l'opération unaire mentionnée par C sur la variable V1.

Nous supposons que l'expression est sous forme de chaîne de caractères terminée par le caractère ".", lue caractère par caractère.

L'algorithme utilise une pile.

    Créerpile(Pile)
    Lire(C)
    Erreur := FAUX
    TANTQUE C # '.' ET NON Erreur :
        SI Opérande(C) : Empiler(Pile, Val(C))
        SINON
            SI Binaire(C) :
                SI NON Pilevide(Pile) :
                    Dépiler(Pile, V1)
                    SI NON Pilevide(Pile) :
                        Dépiler(Pile, V2)
                        Empiler(Pile,Oper1(V1,V2,C)
                    SINON Erreur := VRAI FSI
                SINON Erreur := VRAI FSI
            SINON
                SI Unaire(C):
                    SI NON Pilevide(Pile):
                        Dépiler(Pile,V1)
                        Empiler(Pile, Oper2(V1,C)
                    SINON Erreur := VRAI FSI
                SINON Erreur := VRAI FSI
            FSI
        FSI
    FINTANTQUE

3. Chaînage interne externe

Le fichier est un tableau en mémoire secondaire o� chaque élément a la structure suivante :

    TYPE Typebloc = STRUCTURE
        Tab : Tableau[1..B] DE Typeclé
        Nb : ENTIER
        Lien : ENTIER
    FIN

Typeclé peut être tout ensemble muni d'une relation d'ordre.

Module d'initialisation

La varible R est globale et est utilisée pour la recherche des emplacements libres.

    POUR I =1, M
        Bloc.Nb := 0
        Bloc.Lien := -1
        Ecrirebloc(F, I, Bloc)
    FINPOUR
    R := M

Module de Recherche/insertion

    { Recherche }
    I := H(Clé) + 1
    Lirebloc(F, I, Bloc)
    Continue := VRAI
    TANTQUE Continue :
        Trouv := FAUX ; J := 1;
        TANTQUE NON Trouv ET J <= Bloc.Nb
            SI Bloc.Tab(J) = Clé
                Trouv := VRAI
            SINON J := J + 1 FSI
        FINTANTQUE
        SI Trouv : Continue := FAUX
        SINON
            SI Bloc.Lien # -1 :
                I := Bloc.Lien
                Lirebloc(F, I, Bloc)
            SINON Continue := FAUX FSI
        FSI
    FINTANTQUE

    { Insertion }

    SI Trouv : " Succès"
    SINON
        SI Bloc.Nb < B {Il y a de la place dans le bloc}
            Bloc.Nb := Bloc.Nb + 1
            Bloc.Tab(Bloc.Nb) := Clé
            Ecrirebloc(F, I, Bloc)
        SINON
            {Recherche d'un bloc libre à partir de R }
            Arrêt := FAUX
            TANTQUE R # 0 ET NON Arrêt :
                Lirebloc(F, R, Bloc1) { Utilisation d'un autre buffer }
                SI Bloc.Nb < B :
                    Arrêt := VRAI
                SINON R := R -1 FSI
            FINTANTQUE
            SI R = 0 : " Débordement "
            SINON
                Bloc.Lien := R
                Ecrirebloc(F, I, Bloc)
                Bloc1.Nb := Bloc1.Nb + 1
                Bloc1.Tab(Bloc1.Nb) := Clé
                Ecrirebloc(F, R, Bloc1)
            FSI
        FSI
    FSI