Notación polaca inversa
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[1] 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.[2][3] 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.
Funcionamiento
editarSu 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 las 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 /».
Ventajas
editar- Los cálculos se realizan secuencialmente según se van introduciendo operadores, en vez de tener que esperar a escribir la expresión al completo. Debido a esto, se cometen menos errores al procesar cálculos complejos.
- El proceso de apilación permite guardar resultados intermedios para un uso posterior. Esta característica permite que las calculadoras RPN computen expresiones de complejidad muy superior a la que alcanzan las calculadoras algebraicas.
- No requiere paréntesis ni reglas de preferencia, al contrario que la notación algebraica, ya que el proceso de apilamiento permite calcular la expresión por etapas.
- En las calculadoras RPN, el cálculo se realiza sin tener que presionar la tecla "=" (aunque se requiere pulsar la tecla "Enter" para añadir cifras a la pila).
- El estado interno de la calculadora siempre consiste en una pila de cifras sobre las que se puede operar. Dado que no se pueden introducir operadores en la pila, la notación polaca inversa es conceptualmente más sencilla y menos dada a errores que otras notaciones.
- En términos educativos, la notación polaca inversa requiere que el estudiante comprenda la expresión que se está calculando. Copiar una expresión algebraica directamente a una calculadora sin comprender la aritmética puede dar un resultado erróneo.
Desventajas
editar- La adopción casi universal de la notación algebraica en los sistemas educativos hace que no haya muchas razones prácticas inmediatas para que los alumnos aprendan la notación polaca inversa. No obstante, muchos estudiantes afirman que, una vez aprendida, la notación polaca inversa simplifica en gran manera el cálculo de expresiones complejas.
- Es difícil usar la notación polaca inversa al escribir a mano, dada la importancia de los espacios para separar operandos. Se requiere una caligrafía muy clara para evitar confundir, por ejemplo, 12 34+ (=46) con 123 4+ (=127) o con 1 234+ (=235).
- Las calculadoras RPN son relativamente raras. Forzado a usar una calculadora algebraica, el usuario de una calculadora RPN típicamente comete errores más frecuentemente debido a sus hábitos de uso normales. No obstante, esto no es un problema tan grave en la actualidad, debido a que las calculadoras RPN son fáciles de programar.
El algoritmo RPN
editarEl algoritmo que utilizan las calculadoras RPN es relativamente simple:
- Si hay elementos en la bandeja de entrada:
- Leer el primer elemento de la bandeja de entrada.
- Si el elemento es un operando.
- Poner el operando en la pila.
- Si no, el elemento es una función (los operadores, como "+", no son más que funciones que toman dos argumentos).
- Se sabe que la función x toma n argumentos.
- Si hay menos de n argumentos en la pila
- (Error) El usuario no ha introducido suficientes argumentos en la expresión.
- Si no, tomar los últimos n operandos de la pila.
- Evaluar la función con respecto a los operandos.
- Introducir el resultado (si lo hubiere) en la pila.
- Si hay un solo elemento en la pila:
- El valor de ese elemento es el resultado del cálculo.
- Si hay más de un elemento en la pila:
- (Error) El usuario ha introducido demasiados elementos.
Ejemplo
editarLa 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.
| Entrada | Operación | Pila | Comentario |
|---|---|---|---|
| 5 | Introducir en la pila | 5 | |
| 1 | Introducir en la pila | 5, 1 | |
| 2 | Introducir en la pila | 5, 1, 2 | |
| + | Suma | 5, 3 | Tomar los dos últimos valores de la pila (1, 2), hacer 1 + 2 y sustituirlos por el resultado (3) |
| 4 | Introducir en la pila | 5, 3, 4 | |
| * | Multiplicación | 5, 12 | Tomar los dos últimos valores de la pila (3, 4), hacer 3 * 4 y sustituirlos por el resultado (12) |
| + | Suma | 17 | Tomar los dos últimos valores de la pila (5, 12), hacer 5 + 12 y sustituirlos por el resultado (17) |
| 3 | Introducir en la pila | 17, 3 | |
| − | Resta | 14 | Tomar los dos últimos valores de la pila (17, 3), hacer 17 - 3 y sustituirlos por el resultado (14) |
Al finalizar el cálculo, el resultado (en este caso, 14) aparece como el único elemento en la pila.
Convirtiendo desde la notación de infijo a la notación de postfijo
editarEdsger 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.
Implementaciones
editarHistoria de las implementaciones
editarLa 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.
El RPN en Hewlett-Packard
editarFriden, 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.
El RPN en la Unión Soviética
editarLas calculadoras programables soviéticas (los modelos MK-52, MK-61, B3-34 y el temprano B3-21)[4] usaron el RPN para el modo automático y la programación. Las calculadoras rusas modernas MK-161[5] y MK-152,[6] 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.
Otros datos
editar- HP-15C ha sido posiblemente la calculadora RPN más popular, hasta los puntos de que existe una petición en línea para que HP vuelva a fabricarla[1] ya que adquirir un ejemplar de segunda mano en buen estado de HP-15C cuesta varios cientos de dólares.
- Algunos operadores se usan de forma común en notación posfija, por ejemplo el factorial de x se indica como x!
Véase también
editarReferencias
editar- ↑ "An Analysis of a Logical Machine Using Parenthesis-Free Notation," by Arthur W. Burks, Don W. Warren and Jesse B. Wright, 1954
- ↑ "Charles L. Hamblin and his work" by Peter McBurney
- ↑ "Charles L. Hamblin: Computer Pioneer" by Peter McBurney, July 27, 2008. "Hamblin soon became aware of the problems of (a) computing mathematical formulae containing brackets, and (b) the memory overhead in having dealing with memory stores each of which had its own name. One solution to the first problem was Jan Lukasiewicz's Polish notation, which enables a writer of mathematical notation to instruct a reader the order in which to execute the operations (e.g. addition, multiplication, etc) without using brackets. Polish notation achieves this by having an operator (+, *, etc) precede the operands to which it applies, e.g., +ab, instead of the usual, a+b. Hamblin, with his training in formal logic, knew of Lukasiewicz's work."
- ↑ Elektronika B3-21 page on RSkey.org
- ↑ Elektronika MK-161 page on RSkey.org
- ↑ «MK-152: Old Russian Motive in a New Space Age.». Archivado desde el original el 14 de abril de 2009. Consultado el 20 de septiembre de 2009.
Enlaces externos
editar- RPN or DAL? A brief analysis of Reverse Polish Notation against Direct Algebraic Logic – By James Redin
- Postfix Notation Mini-Lecture – By Bob Brown
- Fith: An Alien Conlang With A LIFO Grammar – By Jeffrey Henning
- Good Ideas, Through the Looking Glass - by Niklaus Wirth
- Ambi browser-based extensible RPN calculator - By David Pratten
- RPN at HP Museum
- RPN Android Muestra la Cadena RPN para android
- Conversor de expresiones algebraicas a RPN
Datos: Q379695
Multimedia: Reverse Polish notation (mathematics) / Q379695
