Notation polonaise inversée - Reverse Polish notation

Postfix-dia.svg

Notation infixe

La notation polonaise inversée ( RPN ), également connue sous le nom de notation polonaise postfixée ou simplement notation postfixée , est une notation mathématique dans laquelle les opérateurs suivent leurs opérandes , contrairement à la notation polonaise (PN), dans laquelle les opérateurs précèdent leurs opérandes. Il n'a pas besoin de parenthèses tant que chaque opérateur a un nombre fixe d'opérandes . La description « polonaise » fait référence à la nationalité du logicien Jan Łukasiewicz , qui a inventé la notation polonaise en 1924.

Le schéma polonais inversé a été proposé en 1954 par Arthur Burks , Don Warren et Jesse Wright et a été réinventé indépendamment par Friedrich L. Bauer et Edsger W. Dijkstra au début des années 1960 pour réduire l' accès à la mémoire de l'ordinateur et utiliser la pile pour évaluer les expressions . Les algorithmes et la notation de ce schéma ont été étendus par le philosophe et informaticien australien Charles L. Hamblin au milieu des années 1950.

Au cours des années 1970 et 1980, Hewlett-Packard a utilisé RPN dans toutes ses calculatrices de bureau et de poche, et a continué à l'utiliser dans certains modèles jusque dans les années 2020. En informatique , la notation polonaise inversée est utilisée dans les langages de programmation orientés pile tels que Forth , STOIC , PostScript , RPL et Joy .

Explication

En notation polonaise inversée, les opérateurs suivent leurs opérandes ; par exemple, pour additionner 3 et 4, on écrirait 3 4 + plutôt que 3 + 4 . S'il y a plusieurs opérations, les opérateurs sont donnés immédiatement après leurs opérandes finaux (souvent un opérateur prend deux opérandes, auquel cas l'opérateur est écrit après le deuxième opérande) ; ainsi l'expression écrite 3 − 4 + 5 en notation conventionnelle s'écrirait 3 4 − 5 + en notation polonaise inversée : 4 est d'abord soustrait de 3, puis 5 lui est ajouté. Un avantage de la notation polonaise inversée est qu'elle supprime le besoin de parenthèses qui sont requises par la notation infixe . Alors que 3 − 4 × 5 peut aussi s'écrire 3 − (4 × 5) , cela signifie quelque chose de très différent de (3 − 4) × 5 . En notation polonaise inversée, le premier pourrait s'écrire 3 4 5 × − , ce qui signifie sans ambiguïté 3 (4 5 ×) − qui se réduit à 3 20 − (qui peut encore être réduit à -17) ; ce dernier pourrait s'écrire 3 4 − 5 × (ou 5 3 4 − × , si on garde un formatage similaire), ce qui signifie sans ambiguïté (3 4 −) 5 × .

Les implications pratiques

En comparaison, le test de la notation polonaise inversée avec la notation algébrique, le polonais inversé s'est avéré conduire à des calculs plus rapides, pour deux raisons. La première raison est que les calculatrices polonaises inversées n'ont pas besoin d'expressions entre parenthèses, donc moins d'opérations doivent être saisies pour effectuer des calculs typiques. De plus, les utilisateurs de calculatrices polonaises inversées ont fait moins d'erreurs que pour d'autres types de calculatrices. Des recherches ultérieures ont clarifié que la vitesse accrue de la notation polonaise inversée peut être attribuée au plus petit nombre de frappes nécessaires pour entrer cette notation, plutôt qu'à une charge cognitive plus faible sur ses utilisateurs. Cependant, des preuves anecdotiques suggèrent que la notation polonaise inversée est plus difficile à apprendre pour les utilisateurs que la notation algébrique.

Conversion à partir de la notation infixe

Article principal: algorithme de triage

Edsger W. Dijkstra a inventé l' algorithme de triage pour convertir les expressions infixes en expressions postfixes (notation polonaise inversée), ainsi nommé parce que son fonctionnement ressemble à celui d'un chantier de triage ferroviaire .

Il existe d'autres façons de produire des expressions postfixes à partir d'expressions infixes. La plupart des analyseurs de priorité d'opérateur peuvent être modifiés pour produire des expressions de suffixe ; en particulier, une fois qu'un arbre syntaxique abstrait a été construit, l'expression suffixe correspondante est donnée par un simple parcours post-ordre de cet arbre.

Implémentations

Histoire

Les premiers ordinateurs à mettre en œuvre des architectures permettant la notation polonaise inverse ont été les Anglais Electric Company de KDF9 machine, qui a été annoncé en 1960 et disponible dans le commerce en 1963, et le Burroughs B5000 , a annoncé en 1961 et a également livré en 1963:

Vraisemblablement, les concepteurs de KDF9 ont puisé leurs idées dans le GEORGE (générateur d'ordre général) de Hamblin , un système de programmation d' autocode écrit pour un ordinateur DEUCE installé à l' Université de Sydney , en Australie, en 1957.

L'un des concepteurs du B5000, Robert S. Barton , a écrit plus tard qu'il avait développé la notation polonaise inversée indépendamment de Hamblin en 1958 après avoir lu un manuel de 1954 sur la logique symbolique par Irving Copi , où il a trouvé une référence à la notation polonaise, qui a fait il a lu les travaux de Jan Łukasiewicz aussi, et avant qu'il ne soit au courant du travail de Hamblin.

Friden a introduit la notation polonaise inversée sur le marché des calculatrices de bureau avec l' EC-130 , conçue par Robert "Bob" Appleby Ragen , prenant en charge une pile à quatre niveaux en juin 1963. Le successeur EC-132 a ajouté une fonction de racine carrée en avril 1965. Vers 1966, la calculatrice Monroe Epic prenait également en charge un schéma d'entrée sans nom ressemblant à RPN.

Hewlett Packard

Article principal: calculatrices HP
Un chapeau promotionnel Hewlett-Packard "No Equals" des années 1980 - à la fois une vantardise et une référence à RPN

Les ingénieurs de Hewlett-Packard ont conçu la calculatrice de bureau 9100A en 1968 avec une notation polonaise inversée avec seulement trois niveaux de pile, une variante de notation polonaise inversée appelée plus tard RPN à trois niveaux . Cette calculatrice a popularisé la notation polonaise inversée parmi les communautés scientifiques et d'ingénierie. Le HP-35 , premier scientifique portable du monde calculatrice , a présenté le classique RPN quatre niveaux en 1972. HP a utilisé la notation inverse polonaise sur chaque calculatrice de poche , il a vendu, que ce soit scientifique, financier ou programmable, jusqu'à ce qu'il a introduit le HP-10 ajouter calculatrice de machine en 1977. À cette époque, HP était le premier fabricant de calculatrices pour les professionnels, y compris les ingénieurs et les comptables.

Les calculatrices ultérieures dotées d'écrans LCD au début des années 1980, telles que la HP-10C , la HP-11C , la HP-15C , la HP-16C et la calculatrice financière HP-12C, utilisaient également la notation polonaise inversée. En 1988, Hewlett-Packard a introduit une calculatrice commerciale, la HP-19B , sans notation polonaise inversée, mais son successeur en 1990, la HP-19BII , a donné aux utilisateurs la possibilité d'utiliser la notation algébrique ou polonaise inversée.

Vers 1987, HP a introduit RPL , un successeur orienté objet de la notation polonaise inversée. Il s'écarte de la notation polonaise inversée classique en utilisant une pile uniquement limitée par la quantité de mémoire disponible (au lieu de trois ou quatre niveaux fixes) et qui peut contenir toutes sortes d'objets de données (y compris des symboles, des chaînes, des listes, des matrices, des graphiques, des programmes , etc.) au lieu de simplement des chiffres. Il a également modifié le comportement de la pile pour ne plus dupliquer le registre supérieur sur les drops (puisque dans une pile illimitée il n'y a plus de registre supérieur) et le comportement de la ↵ Enterclé pour qu'elle ne duplique plus les valeurs en Y sous certaines conditions, les deux font partie de l'ensemble de règles spécifique de la soi-disant pile de mémoire automatique ou de la pile opérationnelle (mémoire) en notation polonaise inversée classique afin de faciliter certains calculs et d'économiser les frappes, mais qui s'étaient avérées également parfois source de confusion chez les utilisateurs non familiarisés avec ces propriétés. De 1990 à 2003, HP a fabriqué la série HP-48 de calculatrices RPL graphiques et, en 2006, a lancé la HP 50g .

En 2011, Hewlett-Packard proposait les modèles de calcul 12C, 12C Platinum, 17bII + , 20b , 30b , 33s , 35s , 48gII (RPL) et 50 g (RPL) qui supportent la notation polonaise inverse. Alors que les calculatrices émulant les modèles classiques continuent de prendre en charge la notation polonaise inversée classique, les nouveaux modèles de notation polonaise inversée proposent une variante de la notation polonaise inversée, où la ↵ Enterclé se comporte comme dans RPL. Cette dernière variante est parfois appelée entrée RPN . En 2013, HP Prime a introduit une forme d'entrée RPN à 128 niveaux appelée RPN avancé . À la fin de 2017, seuls les modèles HP 12C, 12C Platinum, 17bii+, 35s et Prime restent actifs prenant en charge la notation polonaise inversée.

WP 31S et WP 34S

Les calculatrices développées par la communauté WP 31S et WP 34S , qui sont basées sur la plate-forme matérielle HP 20b/HP 30b, prennent en charge la notation polonaise inversée classique de style Hewlett-Packard avec une pile à quatre ou huit niveaux. Une pile à sept niveaux avait été implémentée dans la calculatrice de bureau scientifique MITS 7400C en 1972 et une pile à huit niveaux avait déjà été suggérée par John A. Ball en 1978.

Sinclair Radionique

En Grande - Bretagne, Clive Sinclair de Sinclair scientifique et scientifique programmables modèles utilisés notation inverse polonais.

Commodore

En 1974, Commodore a produit le Minuteman *6 (MM6) sans ↵ Enterclé et le Minuteman *6X (MM6X) avec ↵ Enterclé, tous deux mettant en œuvre une forme de RPN à deux niveaux . Le RPN SR4921 est venu avec une variante de RPN à quatre niveaux avec des niveaux de pile nommés X, Y, Z et W (plutôt que T). Contrairement à l'implémentation de la notation polonaise inversée de Hewlett-Packard, W rempli de 0 au lieu que son contenu soit dupliqué lors de la suppression de la pile.

Prinztronic

Prinz et Prinztronic étaient des noms commerciaux de marque propre de la chaîne de vente au détail de magasins de produits photographiques et électroniques britanniques Dixons , rebaptisés plus tard Currys Digital stores, et sont devenus une partie de DSG International. Une variété de modèles de calculatrices a été vendue dans les années 1970 sous la marque Prinztronic, tous fabriqués pour eux par d'autres sociétés.

Parmi ceux-ci se trouvait la calculatrice scientifique programmable PROGRAM qui comportait une notation polonaise inversée.

Kit de santé

L' ordinateur de navigation d'avion Heathkit OC-1401 / OCW-1401 utilisait un RPN à cinq niveaux en 1978.

Union soviétique

Les calculatrices programmables soviétiques ( MK-52 , MK-61 , B3-34 et modèles antérieurs B3-21 ) utilisaient la notation polonaise inversée pour le mode automatique et la programmation. Les calculatrices russes modernes MK-161 et MK-152 , conçues et fabriquées à Novossibirsk depuis 2007 et proposées par Semico, sont rétrocompatibles avec elles. Leur architecture étendue est également basée sur la notation polonaise inversée.

Autre

Les implémentations existantes utilisant la notation polonaise inversée incluent :

  • Langages de programmation orientés pile tels que :
  • Calculatrices matérielles :
    • Quelques calculatrices Hewlett-Packard scientifiques/d'ingénierie et commerciales/financières
    • Calculatrices Semico
    • Calculatrices SwissMicros
    • Certaines calculatrices APF peuvent également utiliser RPN
  • Calculateurs logiciels :
    • Calculatrice Mac OS X
    • Plusieurs applications Apple iPhone , par exemple "calculatrice de notation polonaise inversée"
    • Plusieurs applications Android par exemple "RealCalc"
    • Plusieurs applications Windows 10 Mobile , par exemple "RPN9"
    • programme de calculatrice système Unix dc
    • Paquet de bibliothèque Emacs lisp calc
    • Calculatrice Xorg ( xcalc )
    • calculatrice scientifique/d'ingénierie grpn utilisant la boîte à outils GIMP ( GTK+ )
    • F-Corrélatifs dans les éléments du dictionnaire MultiValue
    • RRDtool , un logiciel de tabulation et de graphique largement utilisé
    • grdmath, un programme pour les opérations algébriques sur les grilles NetCDF , qui fait partie de la suite Generic Mapping Tools (GMT)
    • galculator, une calculatrice de bureau GTK
    • Calculatrice scientifique/d'ingénierie sans souris Stack-Calculator, y compris les nombres complexes.
    • rpCalc, un simple calculateur de notation polonaise inversé écrit en Python pour Linux et MS Windows et publié sous la licence GNU GPLv2 .
    • orpie, calculateur RPN pour le terminal de nombres réels ou complexes ou de matrices.

Voir également

Les références

Lectures complémentaires

Liens externes