I. Les piles
On donne ci-dessous une possible implémentation de ces fonctions primaire, en utilisant le vocabulaire de la programmation orientée objet que nous avons déjà abordée.
Il existe bien d'autres possibilités pour implémenter ces fonctions primaires.
Dans toute la suite les piles seront affichées entre crochets, comme des list python. Le sommet de la pile est l'élément écrit le plus à droite. Ainsi, si l'on part d'une pile vide, et que l'on empile successivement les entiers 1, puis 2, puis 3, on obtiendra une pile qui s'affichera de la façon suivante : [1, 2, 3]. Le sommet de cette pile est l'entier 3.
Ecrire ci dessous les instructions qui permettent d'obtenir successivement les affichages suivants :
[12] <- sommet [12, 14] <- sommet [12, 14, 8] <- sommet [12, 14] <- sommet [12] <- sommet [] <- sommet
Autre fonction pour les piles
Alice désire écrire une fonction, qui doit retourner la taille de la pile. Attention, une fois que sa taille a été déterminée, la pile ne doit pas avoir été modifiée...
Elle propose le code suivant :
Applications
Le but de cet exercice est d'écrire une fonction qui contrôle si une expression mathématique, donnée sous forme d'une chaîne de caractères, est bien parenthésée, c'est-à-dire s'il y a autant de parenthèses ouvrantes que de fermantes. On s'interdit d'utiliser des variables qui "comptent" les parenthèses ouvrantes ou fermantes.
Par exemple :
- (..(..)..) est bien parenthésée.
- (...(..(..)...) ne l'est pas .
L'algorithme :
On crée une pile. On parcourt l'expression de gauche à droite.
Si on rencontre une parenthèse fermante ")", alors :
- Si la pile n'est pas vide, on dépile
- Sinon on renvoie Faux"
À la fin la pile doit être vide...
Source : Stéphan Van Zuijlen
Compléter la fonction suivante :
