--- 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 {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); } ```