La notación polaca inversa, notación de postfijo, o notación posfija (en inglés, Reverse Polish Notation, o RPN), es un método algebraico alternativo de introducción de datos. Su nombre viene por analogía con la relacionada notación polaca, una notación de prefijo introducida en 1920 por el matemático polaco Jan Łukasiewicz en donde cada operador está antes de sus operandos. En la notación polaca inversa es al revés: primero están los operandos y después viene el operador que va a realizar los cálculos sobre ellos. Tanto la notación polaca como la notación polaca inversa no necesitan usar paréntesis para indicar el orden de las operaciones, mientras la aridad del operador sea fija.
El esquema polaco inverso fue propuesto en 1954 por Burks, Warren y Wright y reinventado independientemente por Friedrich L. Bauer y Edsger Dijkstra a principios de los años 1960, para reducir el acceso de la memoria de computadora y para usar el stack para evaluar expresiones. La notación y los algoritmos para este esquema fueron extendidos por el filósofo y científico de la computación australiano Charles Leonard Hamblin a mediados de los años 1960. Posteriormente, Hewlett-Packard lo aplicó por primera vez en la calculadora de sobremesa HP-9100A en 1968 y luego en la primera calculadora científica de bolsillo, la HP-35. Durante los años 1970 y 1980, el RPN tenía cierto valor incluso entre el público general, pues fue ampliamente usado en las calculadoras de escritorio del tiempo - por ejemplo, las calculadoras de la serie HP-10C.
En ciencias de la computación, la notación de postfijo es frecuentemente usada en lenguajes de programación concatenativos y basados en pila. También es común en sistemas basados en flujo de datos y tuberías, incluyendo las tuberías de Unix.
Su principio es el de evaluar los datos directamente cuando se introducen y manejarlos dentro de una estructura LIFO (Last In First Out), lo que optimiza los procesos a la hora de programar.
Básicamente las diferencias con el método algebraico o notación de infijo es que, al evaluar los datos directamente al introducirlos, no es necesario ordenar la evaluación de los mismos, y que para ejecutar un comando, primero se deben introducir todos sus argumentos, así, para hacer una suma «a+b = c» el RPN lo manejaría «a b +», dejando el resultado c directamente.
Nótese que la notación polaca inversa no es literalmente la imagen especular de la notación polaca: el orden de los operandos es igual en la tres notaciones (infijo, prefijo o polaca, y postfijo o polaca inversa), lo que cambia es el lugar donde va el operador. En la notación infija, el operador va en el medio de los operandos, mientras que en la notación polaca va antes y en la notación polaca inversa va después. Así pues, «640 / 16» (en notación de infijo), se escribe como «/ 640 16» (en notación polaca) y como «640 16 /» en notación polaca inversa. El orden de los operandos es importante cuando se manejan operadores no conmutativos (como la resta o la división), así, si dividimos 10 entre 2, por ejemplo, en las tres notaciones se debe escribir de la siguiente manera: «10 / 2», «/ 10 2», «10 2 /».
El algoritmo que utilizan las calculadoras RPN es relativamente simple:
La expresión algebraica 5+((1+2)*4)-3 se traduce a la notación polaca inversa como 5 1 2 + 4 * + 3 - y se evalúa de izquierda a derecha según se muestra en la siguiente tabla. La «pila» es la lista de los valores que el algoritmo mantiene en su memoria después de realizar la operación dada en la segunda columna.
Al finalizar el cálculo, el resultado (en este caso, 14) aparece como el único elemento en la pila.
Edsger Dijkstra inventó el algoritmo shunting yard (patio de clasificación) para convertir expresiones de infijo al postfijo (RPN), nombrado así porque su operación se asemeja al de un patio de clasificación de ferrocarril.
Hay otras maneras de producir expresiones de posfijo desde la notación de infijo. La mayoría de los parsers de precedencia de operador pueden ser modificados para producir expresiones de posfijo; en particular, una vez que haya sido construido un árbol de sintaxis abstracta, la expresión correspondiente de posfijo es dada por un recorrido postorden de ese árbol.
La primera computadora en implementar la arquitectura que permitía el RPN fue la máquina KDF9 de la compañía English Electric, que fue anunciada en 1960 y entregada (es decir, hecha disponible comercialmente) en 1963, y la Burroughs B5000 de Estados Unidos, anunciada en 1961 y también entregada en 1963. Uno de los diseñadores del B5000, Robert S. Barton, escribió más tarde que él desarrolló el RPN independientemente de Hamblin, en algún momento de 1958 mientras que leía un libro de texto sobre lógica simbólica, y antes de conocer el trabajo de Hamblin.
Friden, Inc. introdujo la notación polaca inversa (RPN) al mercado de las calculadoras de escritorio con el EC-130 en junio de 1963. Los ingenieros de Hewlett-Packard (HP) diseñaron la calculadora de escritorio 9100A con RPN en 1968. Esta calculadora popularizó el RPN entre las comunidades científicas y de ingeniería, aunque los primeros anuncios para el 9100A fallaron en mencionar el RPN. El HP-35, la primera calculadora científica de mano del mundo, usaba RPN en 1972. HP usó el RPN en cada calculadora de mano que vendió, ya fuera científica, financiera, o programable, hasta que introdujo una calculadora al estilo de máquina de adición, el HP-10A. HP introdujo una línea de calculadoras basada en LCD a principios de los años 1980 que usaba RPN, tales como las HP-10C, HP-11C, HP-15C, HP-16C, y la famosa calculadora financiera, la HP-12C. Cuando Hewlett-Packard introdujo una posterior calculadora de negocios, el HP-19B, sin RPN, la retroalimentación de los financieros y otros acostumbrados a la 12-C le obligó a que lanzara el HP-19BII, que dio a los usuarios la opción de usar la notación algebraica o el RPN. Desde 1990 a 2003, HP manufacturó la serie HP48 de calculadoras gráficas RPN y en 2006 introdujo el HP-50g con un LCD de 131x80 píxels y un CPU ARM de 75 MHz que emulaba el CPU HP Saturn de la serie HP-48.
Las calculadoras programables soviéticas (los modelos MK-52, MK-61, B3-34 y el temprano B3-21) usaron el RPN para el modo automático y la programación. Las calculadoras rusas modernas MK-161 y MK-152, diseñadas y manufacturadas en Novosibirsk desde 2007, son compatibles hacia atrás con ellos. Su arquitectura extendida también se basa en la notación polaca reversa.
Escribe un comentario o lo que quieras sobre RPN (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)