Notación posfija (Parte 1: evaluación)

Las expresiones matemáticas normalmente se escriben con notación infija, donde el operador se encuentra entre los dos operandos. La notación posfija, por otro lado, coloca el operador después de los operandos. Como usamos la precedencia de operadores para determinar el orden de cálculo (por ejemplo, la multiplicación/división se evalúa antes que la suma/resta), podemos cambiar la posición de los operandos y eliminar la necesidad de paréntesis:

2 + 5   # Infix
2 5 +   # Postfix

5 + (1 + 2) * 4 - 3   # Infix
5 1 2 + 4 * + 3 -     # Postfix

Las expresiones posfijas se evalúan leyendo de izquierda a derecha. Cada vez que se encuentra un operador, se realiza un cálculo con los dos operandos anteriores. El proceso se repite hasta que no quedan más cálculos por realizar:

2 3 4 * + 9 -   # evaluate 3x4
   2 12 + 9 -   # evaluate 2+12
       14 9 -   # evaluate 14-9
            5   # final answer

Dada una expresión posfija como cadena, devuelve la expresión evaluada. Un solo espacio separa cada operador/operando.

Ejemplos

postfix("12 3 /") ➞ 4

postfix("5 3 4 * +") ➞ 17

postfix("5 3 + 4 *") ➞ 32

Notas

Postfix también se conoce como "Reverse Polish Notation". Consulta la pestaña de recursos para obtener más información.