Application pratique d'une pile : calculatrice

On peut aussi utiliser une pile pour effectuer les calculs d'une expression habituelle. Il va falloir avoir un algorithme un peu plus complexe. Cette algorithme repose sur l'alternance de deux éléments :

• on ajoute les éléments sur la pile
• on vérifie si l'on peut (ou pas) simplifier le sommet de la pile

Prenons par exemple l'expression ( 2 + 3 * 7) * 5. On commence par mettre la parenthèse ouvrante dans la pile, ainsi que le 2, le + et le 3. À ce moment là, on ne peut pas encore simplifier, car la multiplication qui suit est prioritaire. Il faut donc encore empiler le * et le 7. Là, on arrive à la parenthèse fermante. On simplifie ce qui est dedans, on obtient 23 que l'on met en haut de la pile. Il reste ensuite le * et le 5 pour donner au final 115.

L'algorithme est donc le suivant. On parcoure l'expression terme par terme. Pour chaque terme :

• Si c'est un nombre, on place sa valeur dans la pile
• Si c'est une parenthèse ouvrante ( , on la place sur la pile
• Si c'est une parenthèse fermante, on simplifie toutes les opérations possibles au sommet de la pile jusqu'à rencontrer la parenthèse ouvrante. On place alors le résultat sur la pile, après avoir enlevé la parenthèse ouvrante.
• Si c'est un opérateur, on simplifie toutes les opérations au sommet de la pile qui utilisent des opérateurs aussi ou plus prioritaires que cet opérateur. Une fois la simplification faite, on place l'opérateur au sommet de la pile

On voit que cet algorithme est plus compliqué que la notation polonaise inversée. Mais si l'on veut évaluer une expression standard, il faut en passer par là. Vous allez réaliser la calculatrice avec les opérations standard : (), +, -, / , *

Optionnel : Vous pouvez étendre votre calculatrice pour accepter les puissances avec l'opérateur ^. Et (plus difficile),vous pouvez faire une calculatrice qui prend une chaine sans les espaces pour séparer les termes.