La notation polonaise inversée

Une expression arithmétique ne s'évalue pas systématiquement de gauche à droite. Par exemple, l'expression 9+8x7 ne donne pas 17x7=119 mais bien 9+56=65 parce que, par convention, la multiplication est prioritaire sur l'addition. L'utilisation de parenthèses permet de modifier l'ordre d'évaluation d'une expression : dans notre exemple, pour exécuter l'addition avant la multiplication, il suffit d'écrire (9+8)x7.

Mais certains mathématiciens rêvaient de pouvoir se débarrasser des parenthèses. Dans les années 1920, un mathématicien polonais, Jan Lucasievicz, montra qu'il est possible d'éliminer les parenthèses en plaçant les opérateurs avant les opérandes. Il venait d'inventer la notation polonaise, dont l'usage fut toutefois limité à la logique symbolique. Elle est pourtant à l'origine de la notation polonaise inversée (ang. Reverse Polish Notation ou RPN) proposée dans les années 50 par Charles Hamblin, un philosophe australien, à l'origine également de la structure de pile, une structure de données dans laquelle le dernier élément entré est le premier sorti (DEPS ou ang. LIFO : Last In First Out). La RPN intéressa l'industrie informatique naissante, car elle permettait de simplifier l'électronique des circuits logiques et donc de réduire les coûts de fabrication (en échange d'un petit effort d'apprentissage de la part de l'utilisateur). C'est ainsi qu'en 1968, Hewlett-Packard mettait sur le marché la HP9100A, première calculatrice basée sur cette notation.

Ecrire en notation polonaise inversée (on dit aujourd'hui notation postfixée) n'est pas tellement compliqué. En principe, il suffit de placer chaque opérateur juste après ses deux opérandes. Par exemple, 3+4 devient 3 4 +.

Pour obtenir ce résultat, il faut lire l'expression de gauche à droite en extrayant un à un chacun de ses éléments (en jargon informatique anglais, un élément d'une expression est appelé token. Lorsque le token est un opérande, on le place en sortie dans l'expression postfixée. Lorsque le token est un opérateur, on le met de côté. Et lorsqu'il n'y a plus de token en entrée, on va rechercher l'opérateur que l'on concatène à l'expression postfixée.

Appliquons cet algorithme à une expression plus complexe, par exemple 3 + 7 -5 qui comporte deux opérateurs. On a besoin ici d'un mécanisme particulier pour stocker les opérateurs en attendant de les replacer dans l'expression postfixée. Ce mécanisme est une structure de pile (merci Charles !) qui laisse sortir en premier le dernier élément entré. Autrement dit, les opérateurs seront stockés dans l'ordre de lecture +- et ressortiront en ordre inverse -+. L'expression post fixée sera donc 3 7 5-+.

Vous vous demandez certainement comment évaluer l'expression postfixée. Il suffit de la lire de gauche à droite et d'appliquer chaque opérateur aux deux opérandes qui le précèdent. Si l'opérateur n'est pas le dernier, on replace le résultat intermédiaire dans l'expression et on recommence avec l'opérateur suivant. L'expression 3 7 5 - + devient 3 2 + , ce qui donne 5.

Prenons maintenant l'exemple de l'expression 3 * 4 + 2 que l'on convertit en 3 4 2 + * qui s'évalue en 3 6 * = 18 alors que le résultat devrait être 14. La notation postfixée correcte devrait être 3 4 * 2 + qui devient 12 2 +. Pour obtenir l'expression postfixée correcte, il faut ajouter une règle à notre raisonnement : lorsque l'on extrait un opérateur de l'expression infixée, examiner le sommet de la pile. Si la pile est vide, il suffit de placer l'opérateur sur la pile. Si la pile n'est pas vide, alors si l'opérateur qui se trouve au sommet de la pile est prioritaire, placer celui-ci en sortie dans l'expression postfixée et pousser l'opérateur non prioritaire sur la pile.Dans le cas contraire, si l'opérateur au sommet de la pile n'est pas prioritaire, pousser le nouvel opérateur sur la pile au-dessus de celui qui s'y trouve déjà.

Appliquons le raisonnement à l'expression 3 + 4 * 2= 11. Lorsque l'on arrive à l'opérateur *, la pile contient l'opérateur +. Comme l'opérateur * est prioritaire, on le pousse sur la pile qui contient alors +*. On pousse ensuite l'opérande 2 sur le fichier de sortie qui contient alors 3 4 2 et on dépile la pile pour obtenir correctement 3 4 2 * + = 11.

Recommençons avec l'expression 3 * 4 + 2. Lorsque l'on arrive à l'opérateur +, la pile contient l'opérateur *. Comme l'opérateur + n'est pas prioritaire, on enlève * de la pile pour le placer en sortie et on pousse + sur la pile. On continue ensuite avec 2 que l'on place en sortie et on dépile le dernier opérateur de la pile, ce qui donne 3 4 * 2 +.

Revenons à notre problème de départ : comment éliminer les parenthèses. Prenons l'expression 3*(4+2) qui doit se noter 3 4 2 + *. Pour obtenir ce résultat, il faut pousser la parenthèse ouvrante sur la pile qui contiendra donc * ( +. Lorsque l'on rencontre la parenthèse fermante, on dépile la pile jusqu'à ce que l'on retrouve la parenthèse fermante que l'on élimine. Il suffit alors de continuer normalement avec le token suivant.

L'algorithme est donc le suivant

Tant qu'il y a des tokens en entrée {

  1. Examiner le token courant sur le fichier d'entrée
  2. Si c'est un opérande, le placer sur le fichier de sortie
  3. Si c'est une parenthèse ouvrante, la mettre sur la pile
  4. Si c'est un opérateur, alors
    1. Si la pile est vide, pousser l'opérateur sur la pile
    2. Si le sommet de la pile est une parenthèse ouvrante, pousser l'opérateur sur la pile
    3. Si l'opérateur est prioritaire sur celui au sommet de la pile, pousser l'opérateur sur la pile
    4. Sinon, enlever l'opérateur de la pile et le mettre sur le fichier de sortie. Replacer ensuite l'opérateur courant sur la pile
  5. Si c'est une parenthèse fermante, enlever les opérateurs de la pile et les placer sur le fichier de sortie jusqu'à ce que l'on rencontre la parenthèse ouvrante, que l'on élimine.

}

Enlever tous les opérateurs restants et les placer sur le fichier de sortie.

Si vous avez lu jusqu'ici, essayez notre didacticiel Flash

Valid XHTML 1.0 Strict