---
title: "Piles"
date: "2023-12-05"
---

# Rappel

## Qu'est-ce qu'une pile?

. . .

* Structure de données LIFO.

## Quelles fonctionnalités?

. . .

1. Empiler (push): ajouter un élément sur la pile.
2. Dépiler (pop): retirer l'élément du sommet de la pile et le retrouner.
3. Liste vide? (is_empty?).
4. Jeter un oeil (peek): retourner l'élément du sommet de la pile (sans le dépiler).
5. Nombre d'éléments (length).

# Structure de données (1/2)

## Struct `stack`

. . .

```C
#define MAX_CAPACITY 500
typedef struct _stack {
    int data[MAX_CAPACITY]; // les données
    int top;                // indice du sommet
} stack;
```

# Structure de données (2/2)

## Fonctions `stack`

. . .

```C
void stack_init(stack *s) {
    s->top = -1;
}
bool stack_is_empty(stack s) {
    return s.top == -1;
} 
void stack_push(stack *s, int val) {
    s->top += 1;
    s->data[s->top] = val;
}
int stack_pop(stack *s) {
    s->top -= 1;
    return s->data[s->top+1];
}
```

# La pile dynamique

## Comment modifier le code précédent pour avoir une taille dynamique?

. . .

```C
// alloue une zone mémoire de size octets
void *malloc(size_t size); 
// change la taille allouée à size octets (contiguïté garantie)
void *realloc(void *ptr, size_t size);
```

. . .

**Attention:** `malloc` sert à allouer un espace mémoire (**pas** de notion de tableau).

## Et maintenant?

. . .

```C
void stack_create(stack *s); // crée une pile avec une taille par défaut
// vérifie si la pile est pleine et réalloue si besoin
void stack_push(stack *s, int val);
// vérifie si la pile est vide/trop grande 
// et réalloue si besoin
void stack_pop(stack *s, int *ret); 
```

. . .

## Faisons l'implémentation ensemble

# Le tri à deux piles (1/3)

## Cas pratique

![Un exemple de tri à deux piles](figs/tri_piles.svg){width=70%}

# Le tri à deux piles (2/3)

## Exercice: formaliser l'algorithme

. . .

## Algorithme de tri nécessitant 2 piles (G, D)

Soit `tab` le tableau à trier:

```C
pour i de 0 à N-1
    tant que (tab[i] > que le sommet de G)
        dépiler G dans D
    tant que (tab[i] < que le sommet de D)
        dépiler de D dans G
    empiler tab[i] sur G
dépiler tout D dans G
tab est trié dans G
```

# Le tri à deux piles (3/3)

## Exercice: trier le tableau `[2, 10, 5, 20, 15]`

```C
















```

# La calculatrice (1/8)

## Vocabulaire

```C
2 + 3 = 2 3 +,
```

`2` et `3` sont les *opérandes*, `+` l'*opérateur*.

. . .

## La notation infixe

```C
2 * (3 + 2) - 4 = 6.
```

## La notation postfixe

```C
2 3 2 + * 4 - = 6.
```

## Exercice: écrire `2 * 3 * 4 + 2` en notation `postfixe`

. . .

```C
2 3 4 * * 2 + = (2 * (3 * 4)) + 2.
```

# La calculatrice (2/8)

## De infixe à post-fixe

* Une *pile* est utilisée pour stocker *opérateurs* et *parenthèses*.
* Les opérateurs on des *priorités* différentes.

```C
^   : priorité 3
* / : priorité 2
+ - : priorité 1
( ) : priorité 0 // pas un opérateur mais bon
```


# La calculatrice (3/8)

## De infixe à post-fixe: algorithme

* On lit l'expression infixe de gauche à droite.

* On examine le prochain caractère de l'expression infixe.
    * Si opérande, le placer dans l'expression du résultat.
    * Si parenthèse le mettre dans la pile (priorité 0).
    * Si opérateur, comparer sa priorité avec celui du sommet de la pile:
        * Si sa priorité est plus élevée, empiler.
        * Sinon dépiler l'opérateur de la pile dans l'expression du résultat et
          recommencer jusqu'à apparition d'un opérateur de priorité plus faible
          au sommet de la pile (ou pile vide).
    * Si parenthèse fermée, dépiler les opérateurs du sommet de la pile et les
      placer dans l'expression du résultat, jusqu'à ce qu'une parenthèse
      ouverte apparaisse au sommet, dépiler également la parenthèse.
    * Si il n'y a pas de caractère dans l'expression dépiler tous les
      opérateurs dans le résultat.

# La calculatrice (4/8)

## De infixe à post-fixe: exemple

```C
Infixe              Postfixe            Pile    Priorité
((A*B)/D-F)/(G+H)   Vide                Vide    Néant
 (A*B)/D-F)/(G+H)   Vide                (       0
  A*B)/D-F)/(G+H)   Vide                ((      0
   *B)/D-F)/(G+H)   A                   ((      0
    B)/D-F)/(G+H)   A                   ((*     2
     )/D-F)/(G+H)   AB                  ((*     2
      /D-F)/(G+H)   AB*                 (       0
       D-F)/(G+H)   AB*                 (/      2
        -F)/(G+H)   AB*D                (/      2
         F)/(G+H)   AB*D/               (-      1
          )/(G+H)   AB*D/F              (-      1
           /(G+H)   AB*D/F-             Vide    Néant
```

# La calculatrice (5/8)

## De infixe à post-fixe: exemple

```C
Infixe              Postfixe            Pile    Priorité
((A*B)/D-F)/(G+H)   Vide                Vide    Néant
--------------------------------------------------------
           /(G+H)   AB*D/F-             Vide    Néant
            (G+H)   AB*D/F-             /       2
             G+H)   AB*D/F-             /(      0
              +H)   AB*D/F-G            /(      0
               H)   AB*D/F-G            /(+     1
                )   AB*D/F-GH           /(+     1
             Vide   AB*D/F-GH+          /       2
             Vide   AB*D/F-GH+/         Vide    Néant
```

# La calculatrice (6/8)

\footnotesize

## Exercice: écrire le code et le poster sur matrix

* Quelle est la signature de la fonction?

. . .

* Une sorte de corrigé:

```C
char *infix_to_postfix(char* infix) { // init and alloc stack and postfix
    for (size_t i = 0; i < strlen(infix); ++i) {
        if (is_operand(infix[i])) { 
            // we just add operands in the new postfix string
        } else if (infix[i] == '(') { 
            // we push opening parenthesis into the stack
        } else if (infix[i] == ')') { 
            // we pop everything into the postfix
        } else if (is_operator(infix[i])) {
            // this is an operator. We add it to the postfix based 
            // on the priority of what is already in the stack and push it
        }    
    } 
    // pop all the operators from the s at the end of postfix
    // and end the postfix with `\0`
    return postfix;
} 
```


# La calculatrice (7/8)

## Évaluation d'expression postfixe: algorithme

* Chaque *opérateur* porte sur les deux opérandes qui le précèdent.
* Le *résultat d'une opération* est un nouvel *opérande* qui est remis au
  sommet de la pile.

## Exemple

```C
2 3 4 + * 5 - = ?
```

* On parcours de gauche à droite:

```C
Caractère lu        Pile opérandes
    2               2
    3               2, 3
    4               2, 3, 4
    +               2, (3 + 4)
    *               2 * 7
    5               14, 5
    -               14 - 5 = 9
```

# La calculatrice (8/8)

## Évaluation d'expression postfixe: algorithme

1. La valeur d'un opérande est *toujours* empilée.
2. L'opérateur s'applique *toujours* au 2 opérandes au sommet.
3. Le résultat est remis au sommet.

## Exercice: écrire l'algorithme en C (et poster sur matrix)

. . .

```C
bool evaluate(char *postfix, double *val) { // init stack
    for (size_t i = 0; i < strlen(postfix); ++i) {
        if (is_operand(postfix[i])) {
            stack_push(&s, postfix[i]);
        } else if (is_operator(postfix[i])) {
            double rhs = stack_pop(&s);
            double lhs = stack_pop(&s);
            stack_push(&s, op(postfix[i], lhs, rhs));
        }    
    }
    return stack_pop(&s);
}
```