Notación polaca inversa

Notación polaca inversa (RPN), también conocida como notación Łukasiewicz inversa, notación posfija polaca o simplemente La notación posfija es una notación matemática en la que los operadores siguen a sus operandos, en contraste con la notación polaca (PN), en la que los operadores preceden a sus operandos. No necesita paréntesis siempre que cada operador tenga un número fijo de operandos. La descripción "Polaco" se refiere a la nacionalidad del lógico Jan Łukasiewicz, quien inventó la notación polaca en 1924.

La primera computadora que usó la notación sufijo, aunque durante mucho tiempo permaneció esencialmente desconocida fuera de Alemania, fue la Z3 de Konrad Zuse en 1941, así como su Z4 en 1945. El esquema polaco inverso fue propuesto nuevamente en 1954 por Arthur Burks, Don Warren y Jesse Wright y fue reinventado de forma independiente por Friedrich L. Bauer y Edsger W. Dijkstra a principios de la década de 1960 para reducir el acceso a la memoria de la computadora y usar la pila para evaluar expresiones. Los algoritmos y la notación de este esquema fueron ampliados por el filósofo e informático australiano Charles L. Hamblin a mediados de la década de 1950.

Durante las décadas de 1970 y 1980, Hewlett-Packard usó RPN en todas sus calculadoras portátiles y de escritorio, y ha seguido usándolo en algunos modelos hasta la década de 2020. En informática, la notación polaca inversa se utiliza en lenguajes de programación orientados a pilas como Forth, STOIC, PostScript, RPL y Joy.

Explicación

En la notación polaca inversa, los operadores siguen a sus operandos; por ejemplo, para sumar 3 y 4, se escribiría 3 4 + en lugar de 3 + 4. Si hay múltiples operaciones, los operadores se dan inmediatamente después de sus operandos finales (a menudo, un operador toma dos operandos, en cuyo caso el operador se escribe después del segundo operando); por lo que la expresión escrita 3 − 4 + 5 en notación convencional se escribiría 3 4 − 5 + en notación polaca inversa: 4 primero se resta de 3, luego se le suma 5.

El concepto de pila, una construcción de último en entrar/primero en salir, es parte integral de estas acciones. Entonces, en el ejemplo anterior, el 3 se carga en la parte inferior de la pila (el nivel visible) y se presiona una tecla especial por separado (la tecla "Enter ↑& #34; botón en una calculadora HP, por ejemplo) termina esa entrada. Sin esta acción, el 4 se agregaría al 3, dando 34, lo cual no se desea. Cuando se ingresa el 4, el 3 asciende al segundo nivel de la pila; el 3 ahora está encima del 4, actualmente visible. El operador de resta actúa inmediatamente sobre los dos primeros niveles del contenido de la pila, restando el valor inferior del superior, lo que da como resultado -1 en el nivel uno. Esto también finaliza la entrada de datos, por lo que el 5 se puede ingresar inmediatamente. Esto eleva automáticamente el -1 al segundo nivel. Cuando el usuario presiona + (agregar), se agregan los primeros dos niveles y el resultado, 4, aparece en la parte inferior. Esta promoción (y degradación) automática de datos entre niveles en la pila a medida que se realiza cada operación configura automáticamente los operadores sucesivos justo cuando se necesitan.

En las calculadoras HP, la pila tiene cuatro niveles de altura. Entonces es posible escribir 3, Intro ↑, escribir 4, Intro ↑, escribir 5, Ingrese ↑ y escriba 6. La pila ahora contiene los cuatro valores en sus cuatro niveles. Luego se puede presionar el botón + tres veces, y la suma, 18, aparecerá en el nivel uno. Cualquier nueva entrada de datos promueve el 18 al nivel dos. Esta actividad está limitada únicamente por la "altura" de la pila

La administración cuidadosa de la pila permite evaluar expresiones complejas llenas de paréntesis de una forma lineal simple. Rara vez se requiere que los resultados intermedios se almacenen y recuperen, como se requiere generalmente de los sistemas de notación algebraica.

Esta ventaja de la notación polaca inversa es que elimina la necesidad de paréntesis que requiere la notación infija, ya que la pila contiene todos los argumentos en una progresión de último en entrar, primero en salir. Por ejemplo, para calcular la expresión (3 × 4) + (5 × 6), uno escribiría 3, presionaría Intro ↑ y escriba 4. Al presionar × (multiplicar), el producto intermedio 12 aparece visualmente en la parte inferior de la pila. Luego uno teclea 5, Intro ↑, y 6. El resultado intermedio 12 ha sido promovido al nivel tres, con el 5 en el nivel dos y el 6 visible en el nivel uno. Solo se requiere presionar × y luego + en sucesión. El producto intermedio, 30, aparece primero en el nivel uno, y el resultado final, 42, aparece en el nivel uno ya que ahora se ha agregado el 12 en el nivel dos.

Implicaciones prácticas

En comparación, al probar la notación polaca inversa con la notación algebraica, se descubrió que el polaco inverso conduce a cálculos más rápidos, por dos razones. La primera razón es que las calculadoras polacas inversas no necesitan expresiones entre paréntesis, por lo que es necesario ingresar menos operaciones para realizar cálculos típicos. Además, los usuarios de calculadoras polacas inversas cometieron menos errores que con otros tipos de calculadoras. Investigaciones posteriores aclararon que la mayor velocidad de la notación polaca inversa puede atribuirse a la menor cantidad de pulsaciones de teclas necesarias para ingresar esta notación, en lugar de a una menor carga cognitiva en sus usuarios. Sin embargo, la evidencia anecdótica sugiere que la notación polaca inversa es más difícil de aprender para los usuarios que la notación algebraica.

Conversión de notación infija

Edsger W. Dijkstra inventó el algoritmo del patio de maniobras para convertir expresiones infijas en expresiones posteriores (notación polaca inversa), llamado así porque su funcionamiento se parece al de un patio de maniobras de ferrocarril.

Hay otras formas de producir expresiones postfijas a partir de expresiones infijas. La mayoría de los analizadores de precedencia de operadores se pueden modificar para producir expresiones de sufijo; en particular, una vez que se ha construido un árbol de sintaxis abstracta, la expresión de posfijo correspondiente viene dada por un simple recorrido posterior al orden de ese árbol.

Implementaciones

Historia

La primera computadora que implementó una forma de notación polaca inversa (pero sin nombre) fue la Z3 de Konrad Zuse, que comenzó a construir en 1938 y demostró públicamente el 12 de mayo de 1941. En modo de diálogo, permitía operadores para introducir dos operandos seguidos de la operación deseada. Fue destruido el 21 de diciembre de 1943 en un bombardeo. Con la ayuda de Zuse, se construyó una primera réplica en 1961. El Z4 de 1945 también agregó una pila.

Otras primeras computadoras que implementaron arquitecturas que permitían la notación polaca inversa fueron la máquina KDF9 de English Electric Company, que se anunció en 1960 y estuvo disponible comercialmente en 1963, y la Burroughs B5000, anunciada en 1961 y también entregada en 1963:

Presuntamente, los diseñadores de KDF9 tomaron ideas de GEORGE (generador de orden general) de Hamblin, un sistema de programación de autocodificación escrito para una computadora DEUCE instalada en la Universidad de Sydney, Australia, en 1957.

Uno de los diseñadores del B5000, Robert S. Barton, escribió más tarde que desarrolló la notación polaca inversa independientemente de Hamblin en algún momento de 1958 después de leer un libro de texto de 1954 sobre lógica simbólica de Irving Copi, donde encontró una referencia a la notación polaca., lo que le hizo leer también las obras de Jan Łukasiewicz, y antes de conocer la obra de Hamblin.

Friden introdujo la notación polaca inversa en el mercado de las calculadoras de escritorio con la EC-130, diseñada por Robert "Bob" Appleby Ragen, admitiendo una pila de cuatro niveles en junio de 1963. El sucesor EC-132 agregó una función de raíz cuadrada en abril de 1965. Alrededor de 1966, la calculadora Monroe Epic también admitía un esquema de entrada sin nombre que se asemejaba a RPN.

Hewlett-Packard

Un sombrero promocional Hewlett-Packard "No Equals" de la década de 1980 – tanto una jactancia como una referencia a RPN

Los ingenieros de Hewlett-Packard diseñaron la calculadora de escritorio 9100A en 1968 con notación polaca inversa con solo tres niveles de pila con registros de trabajo X ("teclado"), Y ("acumular") y registro de almacenamiento visible Z ("temporal"), una variante de notación polaca inversa a la que más tarde se hará referencia como tres- nivel RPN. Esta calculadora popularizó la notación polaca inversa entre las comunidades científica y de ingeniería. La HP-35, la primera calculadora científica portátil del mundo, introdujo el clásico RPN de cuatro niveles con su función específica conjunto de reglas de la llamada pila operativa (memoria) (más tarde también llamada pila de memoria automática) en 1972. En este esquema, la ↵ Enter duplica los valores en Y bajo ciertas condiciones, y el registro superior se duplica en las gotas para facilitar algunos cálculos y ahorrar pulsaciones de teclas. HP utilizó la notación polaca inversa en todas las calculadoras portátiles que vendía, ya fueran científicas, financieras o programables, hasta que presentó la calculadora de máquina sumadora HP-10 en 1977. En ese momento, HP era el fabricante líder de calculadoras para profesionales, incluidos ingenieros y contadores

Las calculadoras posteriores con pantallas LCD de principios de la década de 1980, como la HP-10C, HP-11C, HP-15C, HP-16C y la calculadora financiera HP-12C, también usaban la notación polaca inversa. En 1988, Hewlett-Packard introdujo una calculadora comercial, la HP-19B, sin notación polaca inversa, pero su sucesora de 1990, la HP-19BII, les dio a los usuarios la opción de usar notación algebraica o polaca inversa nuevamente.

Alrededor de 1987, HP presentó RPL, un sucesor orientado a objetos de la notación polaca inversa. Se desvía de la notación polaca inversa clásica al utilizar una pila limitada únicamente por la cantidad de memoria disponible (en lugar de tres o cuatro niveles fijos) y que podría contener todo tipo de objetos de datos (incluidos símbolos, cadenas, listas, matrices, gráficos, programas, etc.) en lugar de solo números. También cambió el comportamiento de la pila para que ya no duplique el registro superior en las caídas (ya que en una pila ilimitada ya no hay un registro superior) y el comportamiento de Intro ↑ para que ya no duplique los valores en Y, lo que a veces causaba confusión entre los usuarios que no estaban familiarizados con las propiedades específicas de la pila de memoria automática. De 1990 a 2003, HP fabricó la serie HP-48 de calculadoras gráficas RPL y en 2006 presentó la HP 50g.

A partir de 2011, Hewlett-Packard ofrecía los modelos de calculadora 12C, 12C Platinum, 17bII+, 20b, 30b, 33s, 35s, 48gII (RPL) y 50g (RPL) que admiten la notación polaca inversa. Mientras que las calculadoras que emulan los modelos clásicos continúan admitiendo la notación polaca inversa clásica, los nuevos modelos de notación polaca inversa presentan una variante de la notación polaca inversa, donde la tecla Intro ↑ se comporta como en RPL. Esta última variante a veces se conoce como entrada RPN. En 2013, HP Prime introdujo un RPN de entrada de nivel 128 llamado RPN avanzado. A finales de 2017, solo los modelos HP 12C, 12C Platinum, 17bii+, 35s y Prime siguen activos y admiten la notación polaca inversa.

WP 31S y WP 34S

Las calculadoras WP 31S y WP 34S desarrolladas por la comunidad, que se basan en la plataforma de hardware HP 20b/HP 30b, admiten la notación polaca inversa clásica al estilo de Hewlett-Packard con una pila de cuatro u ocho niveles. Se había implementado una pila de siete niveles en la calculadora de escritorio científica MITS 7400C en 1972 y John A. Ball ya sugirió una pila de ocho niveles en 1978.

Radiónica Sinclair

En Gran Bretaña, los modelos Sinclair Scientific y Scientific Programmable de Clive Sinclair utilizaban la notación polaca inversa.

Comodoro

En 1974, Commodore produjo el Minuteman *6 (MM6) sin la tecla enter y el Minuteman *6X (MM6X) con enter , ambos implementando una forma de RPN de dos niveles. El RPN SR4921 vino con una variante de RPN de cuatro niveles con niveles de pila llamados X, Y, Z y W (en lugar de T) y un Ent tecla (para "entrada"). En contraste con la implementación de la notación polaca inversa de Hewlett-Packard, W se llena con 0 en lugar de que su contenido se duplique en las caídas de pila.

Prinztronic

Prinz y Prinztronic eran nombres comerciales de marca propia de la cadena minorista británica de tiendas de productos electrónicos y fotográficos Dixons, más tarde renombrada como tiendas Currys Digital, y pasó a formar parte de DSG. Internacional. En la década de 1970 se vendió una variedad de modelos de calculadoras bajo la marca Prinztronic, todos fabricados para ellos por otras empresas.

Entre estos se encontraba la calculadora científica programable PROGRAM que presentaba notación polaca inversa.

Heathkit

La computadora de navegación de aeronaves Heathkit OC-1401/OCW-1401 usó RPN de cinco niveles en 1978.

Unión Soviética

Las calculadoras programables soviéticas (MK-52, MK-61, B3-34 y modelos anteriores B3-21) usaban la notación polaca inversa tanto para el modo automático como para la programación. Las modernas calculadoras rusas MK-161 y MK-152, diseñadas y fabricadas en Novosibirsk desde 2007 y ofrecidas por Semico, son compatibles con versiones anteriores. Su arquitectura extendida también se basa en la notación polaca inversa.

Otro

Las implementaciones existentes que utilizan la notación polaca inversa incluyen:

• Lenguas de programación orientadas a las etapas tales como:
  • Forth
  • STOIC
  • Factor
  • PostScript página descripción idioma
  • BibTeX
  • Befunge
  • Joy
  • IPTSCRAE
  • fórmulas Lotus 1-2-3 y Lotus Symphony
  • RPL (también lenguaje polaco inverso), un lenguaje de programación para el Commodore PET alrededor de 1979/1981
  • RPL (aka Reverse Polish Lisp), un lenguaje de programación para calculadoras Hewlett-Packard entre 1984 y 2015
  • RPNL (Lengua de Notación Polaca Reversa)
• Calculadoras de hardware:
  • Algunas calculadoras de ciencia/ingeniería y negocios/finanzas Hewlett-Packard
  • Calculadoras semimicos
  • Calculadoras SwissMicros
  • Algunas calculadoras APF también pueden utilizar RPN
• Calculadoras de software:
  • Mac OS X Calculadora
  • Varias aplicaciones de Apple iPhone, por ejemplo "Cálculo de notación de pulido reverso"
  • Varias aplicaciones Android, por ejemplo "RealCalc"
  • Varias aplicaciones móviles de Windows 10, por ejemplo "RPN9"
  • Programa de cálculo del sistema Unix dc
  • Emacs lisp biblioteca paquete calc
  • Calculadora de Xorg (xcalc)
  • ARPCalc, una potente calculadora científica/ingeniería RPN para Windows, Linux y Android que también tiene una versión basada en web-browser.
  • calculadora científica/ingeniería de grpn utilizando el kit de herramientas GIMP (GTK+)
  • F-Correlatives in Multi Valor del diccionario
  • RRDtool, un software de tabulación y graficado ampliamente utilizado
  • grdmath, un programa para operaciones algebraicas en redes NetCDF, parte de la suite Herramientas de Mapping Genérico (GMT)
  • galculador, una calculadora de escritorio GTK
  • Calculadora científica/ingeniería sin manchas, incluyendo números complejos.
  • rpCalc, una simple calculadora de notación de pulido inverso escrita en Python para Linux y MS Windows y publicada bajo la licencia GNU GPLv2.
  • orpie, calculadora RPN para el terminal para números reales o complejos o matrices.
• Bibliotecas de clase
  • TRURL, una biblioteca de clases para la construcción de calculadoras RPN en Object Pascal.