Notacion Polaca inversa

 ¿Qué significa la notación polaca inversa (RPN)?

La notación polaca inversa (RPN) es un método para transmitir expresiones matemáticas sin el uso de separadores como corchetes y paréntesis. En esta notación, los operadores siguen sus operandos, eliminando así la necesidad de corchetes para definir la prioridad de evaluación. La operación se lee de izquierda a derecha, pero la ejecución se realiza cada vez que se alcanza un operador, y siempre utilizando los dos últimos números como operandos. Esta notación es adecuada para computadoras y calculadoras, ya que hay menos caracteres para rastrear y menos operaciones para ejecutar.

Techopedia explica la notación polaca inversa (RPN)

La notación polaca inversa fue propuesta por Burks, Warren y Wright en 1954 y se llamó así porque era simplemente el reverso de la notación polaca (notación de prefijo), inventada por el lógico polaco Jan Lukasiewicz, que coloca al operador antes que los operandos. En la década de 1960, EW Dijkstra y FL Bauer lo reinventaron de forma independiente para reducir la cantidad de veces que se accede a la memoria de la computadora y aumentar el rendimiento. Hizo uso de la pila de la computadora para almacenar sus operandos antes de ejecutar el operador.

RPN lleva a cálculos más rápidos por un par de razones. Una es que hay menos información para almacenar. Por lo tanto, en lugar de necesitar almacenar nueve caracteres para la expresión ((5 - 3) * 2), las computadoras que usan RPN solo necesitan almacenar cinco caracteres con la expresión 5 3 - 2 *. Y debido a que hay menos caracteres para procesar, la ejecución se vuelve más rápida.

Entonces, en una computadora que usa RPN, la evaluación de la expresión 5 1 - 3 * es la siguiente:

1. Empuja 5 en la pila. Este es el primer valor.
2. Empuja 1 en la pila. Este es el segundo valor y está en la posición por encima del 5.
3. Aplique la operación de resta tomando dos operandos de la pila (1 y 5). El valor superior (1) se resta del valor debajo de él (5), y el resultado (4) se almacena de nuevo en la pila. 4 es ahora el único valor en la pila y está en la parte inferior.
4. Empuja 3 en la pila. Este valor está en la posición superior a 4 en la pila.
5. Aplique la operación de multiplicación quitando los dos últimos números de la pila y multiplicándolos. El resultado se vuelve a colocar en la pila. Después de esta operación, la pila ahora solo contiene el número 12.

La notación polaca inversa (en inglés, Reverse Polish Notation, o RPN), es una forma alternativa de escribir expresiones matemáticas. Por ejemplo, la expresión "20 - (4 + 3) * 2" en RPN es "20 4 3 + 2 * -".

Para evaluar una expresión en RPN, usamos una lista auxiliar (inicialmente vacía) y recorremos la expresión de izquierda a derecha. Cada vez que encontramos un número, lo añadimos a la lista auxiliar. Cuando encontramos un operador, retiramos los dos números que hay al principio de la pila, utilizamos el operador con ellos y los quitamos de la lista y le añadimos el resultado. Cuando alcancemos el final de la expresión, debemos tener un solo número en la lista auxiliar si la expresión estaba bien formada, y éste representa el resultado de la expresión. Por ejemplo, la evaluación de RPN "20 4 3 + 2 * -" es la siguiente: