RPN: Algoritmo, métodos y ejemplos

RPN una vez formada la base de un programador de computadoras en el mundo. Hoy en día no es tan bien conocido. Por lo tanto, ejemplo cómico, que representa una "marcha atrás" rollos de salchicha polaca fuera, todavía puede ser mal interpretado por algunos programadores con conocimientos. No muy bien explicar la broma, pero en este caso será plenamente justificado.

infijo

Todos los programadores, y la mayoría de los estudiantes están familiarizados con el uso de los operadores. Por ejemplo, los valores de la expresión x + de suma de las variables x e y signo más usado. Menos conocido es el hecho de que este es tomado de las matemáticas notación, llamada notación infija, de hecho, es un gran problema para las máquinas. Este operador recibe como entrada dos valores se registran en la izquierda y la derecha. En la programación de la notación utiliza opcionalmente con las operaciones de los signos. Por ejemplo, x + y puede ser escrito como una función de plegado (x, y), en el que el compilador y eventualmente convierte notación infija. Sin embargo, todo el mundo sabe la matemática es demasiado bueno para no usar expresiones aritméticas, que forman una especie de mini-lenguaje interno en casi cualquier lenguaje de programación.

Traductor fórmula

El primer lenguaje de programación Fortran verdadero éxito se ha convertido en tan gran medida debido a que la expresión aritmética (es decir fórmula ..) Se convirtió (broadcast) en el código, de ahí el nombre de ella – Fórmula traducción. Antes de eso, tenían que escribir, por ejemplo, doblado en forma de funciones (y multiplicar (b, c)). En el problema de la aplicación de COBOL fórmula de conversión automática se consideró muy difícil porque los programadores tenían que escribir cosas como Añadir la A a la B Mutliply Por C.

¿Qué pasa con infija?

El problema es, que los operadores tienen propiedades tales como la precedencia y asociatividad. Debido a esto, la definición de la función infija se convierte en tarea no trivial. Por ejemplo, la multiplicación tiene mayor precedencia que la adición o sustracción, lo que significa que la expresión 2 + 3 * 4 no es igual a la suma de 2 y 3, multiplicado por 4, como lo sería en el desempeño de los operadores de izquierda a derecha. De hecho, multiplicar 3 por 4 y añadir 2. Este ejemplo ilustra que el cálculo de la expresión infija a menudo requiere un cambio en el orden de operadores y operandos. Además, es necesario utilizar llaves para buscar notación más clara. Por ejemplo, (2 + 3) * (4 + 5) no se puede escribir sin los paréntesis, porque 2 + 3 * 4 + 5 significa que es necesario multiplicar 3 por 4 y añadir 2 y 5.

El orden en el que se desea calcular los operadores requiere un largo recuerdo. Debido a esto, los estudiantes que empiezan a aprender aritmética, a menudo obtienen resultados erróneos, incluso si las operaciones reales se realizan correctamente. Es necesario enseñar el orden de las declaraciones de acciones de memoria. En primer lugar, la acción debe llevarse a cabo entre paréntesis, a continuación, multiplicación y división, y, finalmente, la suma y la resta. Pero hay otra forma de escribir expresiones matemáticas como notación infija es sólo una de las posibles pequeñas "lenguas" que se pueden agregar a más.

Prefijo y de sufijo notación

Dos de las alternativas más conocidas es registrar el operador antes o después de sus operandos. Se les conoce como la notación de prefijo y de sufijo. El lógico Yan Lukasevich inventó la primera de ellas en 1920. Vivió en Polonia, por lo que el disco se llama polaca. versión de Postfix, respectivamente, llamado notación polaca inversa (ARF). La única diferencia entre estos dos métodos es la dirección en la que al leer el registro (de izquierda a derecha o de derecha a izquierda), por lo que basta considerar en detalle sólo uno de ellos. El operador de OPN está escrito después de que sus operandos. Por lo tanto, la expresión AB + representa un ejemplo RPN para A + B.

número ilimitado de operandos

La ventaja inmediata de la notación es que resume el operador n-adic y la notación infija es realmente sólo funciona con dos operandos, t. E. son inherentemente adecuado sólo para operaciones binarias. Por ejemplo, ABC @ es la expresión polaca inversa usando marca triádica que es el valor máximo de A, B y C. En este caso, el operador actúa sobre la izquierda de las tres operando sí mismo y corresponde a una llamada de función @ (A, B, C). Si intenta escribir el símbolo @ como infija, tales como A @ AC o algo por el estilo, se hace evidente que simplemente no funciona.

La prioridad dada por el orden

RPN tiene otra ventaja en que la prioridad de los operadores puede ser representado por el orden de su aparición. Al mismo tiempo nunca necesitar aparatos ortopédicos, aunque pueden ser incluidos como operaciones de caracteres para facilitar la conversión de notación infija. Por ejemplo, AB + C * – equivalente inequívoca (A + B) * C, por lo que la multiplicación no se puede calcular hasta que la adición realizada, lo que da un segundo operando para la multiplicación. Es decir, si el calculado AB + C * por un operador a la vez, obtenemos AB + C * -> (AB +) * C -> (A + B) * C

algoritmo de cálculo

El operador de OPN se ve igual que una función que toma como argumentos dos valores escritos en su izquierda. Además, es una notación natural para su uso en lenguajes de programación, como el método de cálculo corresponde a las operaciones de la pila y la necesidad de análisis se elimina. Por ejemplo, el descargador en la expresión 5 + 6 * 7 aparecerá como 5, 6, 7 *, +, y puede ser calculada simplemente mediante la exploración de izquierda a derecha y escribir los valores en una pila. Siempre que un signo común de operación, seleccionado por el elemento superior 2 de la memoria del ordenador, el operador se utiliza y el resultado devuelto a la memoria. Cuando el resultado final de la expresión de cálculo estará en la parte superior de la pila.

Por ejemplo:

• S = () 5, 6, 7, *, + 5 colocado en la pila.
• S = (5) 6, 7, *, + 6 colocado en la pila.
• S = (5, 6), 7 *, 7 + colocar la pila.
• S = (5, 6, 7), * 2 + elegir los valores de la pila, el uso * y colocar el resultado en la pila.
• S = (5, 6 * 7) = (5, 42) + 2 valores seleccionados de la pila, para aplicar el + y poner el resultado en la pila.
• S = (5 + 42) = (47) de cálculo se completa, el resultado se almacena en la parte superior de la pila.

Este algoritmo se puede comprobar RPN en varias ocasiones, pero cada vez que va a funcionar, independientemente de la complejidad de la expresión aritmética.

OPN y las pilas están estrechamente vinculados. Este ejemplo muestra cómo utilizar la memoria para calcular el valor de la notación polaca inversa. Menos obvia es que se puede utilizar la pila, convertir expresión infija estándar en la insuficiencia renal aguda.

Ejemplos de lenguajes de programación

Pascal RPN se dio cuenta de como esto (muestra la parte del programa).

Para leer los números y operadores en el ciclo llamado procedimiento, que determina si el número o signo operación token. En el primer caso, el valor almacenado en la pila, y el segundo de los dos números de pila superiores acción correspondiente se lleva a cabo y el resultado se almacena.

toktype: = num;

leer (s);

si c en [ '+', '-', '*', '/'] luego comenzar

Si EOLN continuación, CN: = '' otra lectura (CN);

si cn = '' entonces

caso de una

'+': Toktype: = sumar; '-': toktype: = sub;

'*': Toktype: = mul; '/': Toktype: = div

final

else begin

si a = '-' entonces sgn: = -1 Error otra cosa: = c '+';

con: = cn

final

terminar;

si (no error) y (toktype = num) entonces obtieneNumero;

Si toktype num luego comenzar

y = pop; x: = pop;

si no es error, entonces

caso de toktype

añadir: z: = x + y; substitución: z: = x-y; mul: z: = x * y; div: z: = x / y

final

push (z);

RPN C-aplicación (parte mostrada del programa):

(s = strtok (s, w); s; s = strtok (0, w)) {

a = strtod (s, y e);

si (e> s) de empuje (a);

#define rpnop (x) printf ( "% c:", * s), b = pop (), a = pop (), push (x)

else if (* s == '+') rpnop (a + b);

else if (* s == '-') rpnop (a – b);

else if rpnop (* s == '*') (a * b);

else if (* s == '/') rpnop (a / b);

rpnop #undef

}

implementaciones de hardware

En aquellos días, cuando la tecnología informática era muy caro, se pensó una buena idea para obligar a la gente a utilizar descargadores de sobretensión. En 1960-s., Como ahora, era posible comprar las calculadoras, que trabajan en notación polaca inversa. Para añadir 2 y 3 de ellos debe introducir 2, luego 3, y presione el botón "más". A primera vista, los operandos de entrada para el operador parecían complicados y difíciles de recordar, pero después de un mientras que algunos son adictos a esta forma de pensar y no podía entender por qué los otros insisten en infija estúpida, que es tan complicado y así es limitada.

compañía Burroughs incluso construyó un mainframe, que no tenía otra memoria, excepto pila. La única cosa que hace la máquina – aplicar los algoritmos y métodos RPN a la pila central. Todas sus operaciones fueron considerados como operadores pararrayos, que se aplica a los valores de n superiores. Por ejemplo, el equipo tomó la Dirección de devolución de la parte superior de la pila, y así sucesivamente. D. La arquitectura de una máquina de este tipo era simple, pero no lo suficientemente rápido como para competir con las arquitecturas más comunes. Muchos, sin embargo, todavía lamentar el hecho de que un enfoque sencillo y elegante a la informática donde cada programa era una expresión de OPN, encuentra su continuación.

Uno calculadoras de tiempo con RPN eran populares, y algunas personas todavía les dan preferencia. Además, desarrollaron un orientado a pila idiomas, como el Forth. Hoy en día es poco utilizado, pero todavía nostálgica de sus antiguos usuarios.

Entonces, ¿cuál es el significado chistes sobre la salchicha polaca inversa?

Si asumimos que el operador de la salchicha, la notación infija, debe estar dentro del rollo como en el perro caliente convencional. El RPN se encuentra justo en dos mitades entre ellas consiguen listos después de cálculo. Ahora viene la parte difícil – mostaza. Ella ya está en la salchicha, t. E. Ya calcula como un operador unario. Se cree que la mostaza también debe ser mostrado como falta de cálculo y por lo tanto se debe mover a la derecha de la salchicha … Pero es posible, esto requeriría demasiado grande pila de …