Notación polaca inversa

La notaciones de prefijo (o polaca, en homenaje a Jan Łukasiewicz), de infijo y de postfijo (o polaca inversa) son formas de escritura de expresiones algebraicas que se diferencian por la posición relativa que toman los operadores y los operandos. En la notación de prefijo, el operador se escribe delante de los operandos (+ 3 4), entre los operandos en la notación de infijo (3 + 4) y tras los operandos en la de posfijo (3 4 +).

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.

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.

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.