Notation Polonaise Inverse : Une alternative élégante pour évaluer les expressions mathématiques
La Notation Polonaise Inverse (NPI) représente une méthode performante pour l'évaluation d'expressions mathématiques, se distinguant par le positionnement des opérateurs après leurs opérandes. Cette technique rend possible l'omission des parenthèses, ce qui simplifie et clarifie le déroulement du calcul. Même si elle peut paraître inhabituelle au début, l'emploi de la NPI dynamise considérablement la réalisation des opérations, notamment dans les systèmes informatiques et les calculatrices programmables.
Il existe de nombreuses façons d'écrire des expressions mathématiques. La plus courante est la notation infixée, où les opérateurs sont placés entre les opérandes, comme dans A + B ou (C D) - E. Bien que cette notation puisse nous sembler intuitive, à nous humains, elle n'est pas nécessairement la solution la plus optimale pour les ordinateurs et les calculatrices. Dans cet article, nous allons examiner une alternative moins connue, mais sans doute plus élégante : la Notation Polonaise Inverse (NPI), également appelée notation postfixée.
Qu'est-ce que la Notation Polonaise Inverse ?
La NPI est une notation mathématique où les opérateurs suivent leurs opérandes. Au lieu d'écrire A + B, en NPI, nous l'écrivons A B +. Cela peut sembler inhabituel au premier abord, mais ses avantages deviennent rapidement évidents.
Le concept de la NPI trouve son origine chez le mathématicien polonais Jan Łukasiewicz, qui a développé la notation préfixée (notation polonaise) dans les années 1920, où les opérateurs précèdent leurs opérandes. La notation postfixée est une variation de celle-ci, développée plus tard par l'informaticien australien Charles Hamblin dans les années 1950 pour simplifier le traitement informatique.
Pourquoi la NPI est-elle utile ?
Les principaux avantages de la NPI sont la suppression de l'ambiguïté et l'efficacité de calcul. La notation infixée nécessite des parenthèses pour clarifier l'ordre des opérations, et les ordinateurs ont besoin d'algorithmes d'analyse syntaxique complexes pour gérer correctement la priorité des opérateurs. En NPI, cependant, les parenthèses sont inutiles, et l'ordre des opérations est automatiquement déterminé par la structure de l'expression.
Cela était particulièrement crucial pour les premiers ordinateurs et les calculatrices de poche où les ressources matérielles étaient limitées. Les calculatrices utilisant la NPI pouvaient effectuer des calculs plus simplement et plus rapidement.
Anecdote historique : La notation NPI a été popularisée pour la première fois par Hewlett-Packard (HP) dans les années 1960 et 70. La calculatrice de bureau HP-9100A (1968) a été l'une des premières calculatrices disponibles dans le commerce à utiliser la NPI. Plus tard, la légendaire HP-35 (1972), la première calculatrice de poche scientifique, a également employé la NPI, et cette méthode est devenue une marque distinctive des calculatrices professionnelles de HP pendant longtemps. Les calculatrices NPI étaient réputées pour leurs calculs rapides et précis et ont gagné une grande popularité auprès des ingénieurs, des scientifiques et des professionnels de la finance.
Comment fonctionne la NPI
Examinons un exemple de fonctionnement de la NPI. Prenons l'expression infixée : (3 + 4) 2 - 5.
Tout d'abord, nous convertissons cette expression en NPI. Pour la conversion, nous devons tenir compte de l'ordre des opérations. Dans ce cas, nous effectuons d'abord l'addition entre parenthèses, puis nous multiplions par deux, et enfin nous soustrayons cinq. L'expression NPI sera : 3 4 + 2 5 -.
Voyons maintenant comment évaluer cette expression NPI à l'aide d'une pile. Une pile est une structure de données dans laquelle les éléments peuvent être placés (empiler) et retirés (dépiler), en retirant toujours l'élément inséré en dernier (LIFO - Last-In, First-Out).
Évaluation étape par étape de l'expression NPI :
3: Lire3. C'est un opérande, empilez-le sur la pile. État de la pile :[3]4: Lire4. Également un opérande, empilez-le sur la pile. État de la pile :[3, 4]+: Lire l'opérateur+. Dépilez deux opérandes de la pile (d'abord4, puis3). Effectuez l'addition :3 + 4 = 7. Empilez le résultat (7) sur la pile. État de la pile :[7]2: Lire2. Opérande, empilez-le sur la pile. État de la pile :[7, 2]: Lire l'opérateur. Dépilez deux opérandes de la pile (d'abord2, puis7). Effectuez la multiplication :7 2 = 14. Empilez le résultat (14) sur la pile. État de la pile :[14]5: Lire5. Opérande, empilez-le sur la pile. État de la pile :[14, 5]-: Lire l'opérateur-. Dépilez deux opérandes de la pile (d'abord5, puis14). Effectuez la soustraction :14 - 5 = 9. Empilez le résultat (9) sur la pile. État de la pile :[9]
Puisque nous avons atteint la fin de l'expression NPI et qu'il ne reste qu'un seul élément sur la pile, cet élément est le résultat final. Ainsi, la valeur de l'expression (3 + 4) 2 - 5 évaluée en NPI est 9.
Comment convertir des expressions infixées en NPI ?
L'algorithme le plus courant pour convertir les expressions infixées en NPI est l'algorithme du Shunting-yard, développé par Edsger Dijkstra. Cet algorithme utilise une pile (pour les opérateurs et les parenthèses) et une file d'attente de sortie (qui peut simplement être une liste en pratique) pour la conversion.
Étapes de l'algorithme du Shunting-yard :
- Tokenisation : Décomposer l'expression infixée en tokens (nombres, opérateurs, parenthèses).
- Initialisation : Créer une pile vide pour stocker les opérateurs et une file d'attente de sortie vide pour construire l'expression NPI.
- Traitement des tokens : Parcourir les tokens :
- Nombre : Si le token est un nombre, ajoutez-le à la file d'attente de sortie.
- Opérateur (op1) : Si le token est un opérateur :
- Tant qu'il y a un opérateur (op2) au sommet de la pile, ET soit :
- op2 a une priorité supérieure à op1, SOIT
- op2 a une priorité égale à op1 ET op1 est associatif à gauche (dans notre exemple, tous les opérateurs sont associatifs à gauche),
- Dépilez op2 de la pile et ajoutez-le à la file d'attente de sortie.
- Empilez op1 sur la pile.
- Tant qu'il y a un opérateur (op2) au sommet de la pile, ET soit :
- Parenthèse gauche
(: Empilez-la sur la pile. - Parenthèse droite
):- Tant que l'opérateur au sommet de la pile n'est pas une parenthèse gauche :
- Dépilez l'opérateur de la pile et ajoutez-le à la file d'attente de sortie. (Si la pile devient vide avant de trouver une parenthèse gauche, il y a une erreur de correspondance.)
- S'il y a une parenthèse gauche au sommet de la pile, dépilez-la de la pile (mais ne l'ajoutez pas à la file d'attente de sortie - les parenthèses ne sont pas incluses dans l'expression NPI).
- Si le sommet de la pile n'est pas une parenthèse gauche après le traitement de la parenthèse droite, alors les parenthèses ne correspondent pas.
- Tant que l'opérateur au sommet de la pile n'est pas une parenthèse gauche :
- Vider la pile : Lorsqu'il n'y a plus de tokens à lire, dépilez tous les opérateurs restants de la pile et ajoutez-les à la file d'attente de sortie.
- Résultat : La file d'attente de sortie contient maintenant l'expression NPI.
Priorité et associativité :
Il est important de comprendre la priorité et l'associativité des opérateurs. L'ordre de priorité habituel (du plus élevé au plus faible) :
- Multiplication (
), Division (/) - Addition (
+), Soustraction (-)
Les quatre opérations arithmétiques de base sont associatives à gauche, ce qui signifie que les opérateurs de même priorité sont évalués de gauche à droite (par exemple, a - b - c = (a - b) - c).
Exemple de conversion de l'expression infixée (3 + 4) 2 - 5 en NPI à l'aide de l'algorithme du Shunting-yard :
| Token | File d'attente de sortie | Pile d'opérateurs | Remarque |
|---|---|---|---|
( | ( | Parenthèse gauche empilée sur la pile. | |
3 | 3 | ( | Nombre ajouté à la file d'attente de sortie. |
+ | 3 | (, + | Opérateur empilé sur la pile. |
4 | 3, 4 | (, + | Nombre ajouté à la file d'attente de sortie. |
) | 3, 4, + | ( | Parenthèse droite : dépiler les opérateurs (+) vers la file d'attente jusqu'à ce qu'une parenthèse gauche soit trouvée. Dépiler la parenthèse gauche. |
| 3, 4, + | | Opérateur empilé sur la pile (la pile était vide). |
2 | 3, 4, +, 2 | | Nombre ajouté à la file d'attente de sortie. |
- | 3, 4, +, 2, | - | Opérateur : - sur la pile. |
5 | 3, 4, +, 2, 5 | - | Nombre ajouté à la file d'attente de sortie. |
| Fin | 3, 4, +, 2, 5, - | Fin de l'entrée : dépiler les opérateurs restants (-) de la pile vers la file d'attente. |
Ainsi, la forme NPI de l'expression infixée (3 + 4) 2 - 5 est : 3 4 + 2 * 5 -.
Résumé
La Notation Polonaise Inverse est une méthode élégante et efficace pour écrire et évaluer des expressions mathématiques. Bien qu'elle puisse sembler moins intuitive que la notation infixée au premier abord, la NPI offre plusieurs avantages, en particulier pour le traitement informatique. Elle supprime l'ambiguïté, ne nécessite pas de parenthèses et peut être évaluée efficacement à l'aide d'une simple pile. L'algorithme du Shunting-yard fournit une méthode largement utilisée et efficace pour convertir les expressions infixées en NPI.
Sa signification historique est indéniable, ayant joué un rôle important dans les premières calculatrices de poche, et elle reste un concept pertinent en informatique aujourd'hui, utilisé dans les compilateurs et les machines virtuelles. Bien que moins courante dans l'usage quotidien, la NPI est un outil précieux et une façon de penser qui offre une compréhension plus profonde de la relation entre les expressions mathématiques et les opérations informatiques.