Beneficios de aprender Notación Polaca Inversa

La pila (stack) es una de las estructuras de datos fundamentales en programación, una especie de “pozo” en el que vamos arrojando datos que pueden recuperarse de forma secuencial en el mismo orden que entraron en la pila. El problema es que muchas personas la encuentran poco intuitiva y difícil de usar. ¿Cómo resolverlo?

El uso de pilas está sumamente extendido en el mundo de la programación; la tenemos en las librerías básicas de Java, por ejemplo al usar colecciones, y es casi obligatorio comprenderlas para programar en lenguaje R, una de las piedras angulares en Big Data. Pero claro, como acabo de decir, en los cursos me encuentro a menudo con personas a las que les resulta difícil coger el truco a eso de trabajar con un acumulador de acceso lineal. Tanto si es tu caso como si quieres mejorar tu rapidez mental al comprender el desarrollo de un programa, quiero recomendarte algo para que las pilas dejen de ser un problema.

El problema del uso de pilas es que son contrarias a la notación matemática que hemos aprendido en la escuela, intuitiva y fácil de aplicar. Si queremos sumar dos números, dos y dos, por ejemplo, decimos “dos más dos igual a cuatro” y eso tiene una traslación sencilla en notación algebraica: “2 + 2 = 4”.

Al escribir programas imperativos, en los que las instrucciones siguen una secuencia de órdenes, tendemos a pensar de esta forma, una orden detrás de otra, y los compiladores están hechos para que las secuencias de asignación sean más o menos de esta forma: “int i = 2 + 2”. Pero claro, llega un momento en que hay que lidiar con una pila, un acumulador, en el que se “echan” datos sin pensar mucho en ellos y luego la operativa del programa los va utilizando. ¡Dios mío! ¿Y si no hay datos? ¿Cómo sé cuál es el operador que se aplica a cada uno de ellos?

Estas dudas son habituales y surgen de la falta de familiaridad con el funcionamiento de las pilas. Para resolverlo, el truco está en convertir el uso de pilas en algo cotidiano. Pero claro, ¿dónde tenemos acumuladores de pila? Pues en una cosa tan curiosa como los emuladores de calculadoras antiguas.

En la década de los años 20 Jan Lukasiewicz, un matemático polaco, desarrolló una notación en la que el operador se indicaba ANTES que los operandos. Si querías sumar dos más dos, lo indicabas de esta forma: “+ 2 2”. El resultado era cuatro, igual que ahora. Puede parecer complicado, pero el caso es que la Notación Polaca, que así se denominó, eliminaba la necesidad de usar paréntesis en las expresiones para aclarar las reglas de precedencia.

Cuarenta años después, dos equipos independientes con varios años de diferencia recuperaron esta propuesta y la redefinieron invirtiendo el orden de los elementos; es decir, se ponía primero los operandos y luego el operador asociado. De esta forma, dos más dos se indica “2 2 +”. El resultado sigue siendo cuatro 😉 El motivo de este cambio es que de esta forma se podía simplificar mucho el diseño de las máquinas de cómputo electrónico mediante el uso de… PILAS. Una pila gestionada con Notación Polaca Inversa permite introducir las expresiones más complejas sin necesidad de un intérprete que evalúe la precedencia entre operadores o paréntesis, lo que reduce muchísimo la complejidad de los circuitos electrónicos.

En la Wikipedia puedes ver un ejemplo muy bueno del uso de pilas para despejar la expresión “5 + ((1 + 2) × 4) − 3”, que escrita en RPN (Reverse Polish Notation) queda como “5 1 2 + 4 × + 3 −”. ¿Complicado? No lo creas. Raro, pero no complicado. Se trata más bien de una cuestión de hábito. Si sólo lo haces una o dos veces, es incómodo, pero si lo haces a diario terminas por realizarlo con toda normalidad.

¿Y dónde podemos encontrar algo cotidiano que use RPN? A mediados de los años 60, Hewlett Packard lanzó su primera línea de “ordenadores de sobremesa”, calculadoras estadísticas que podían realizar operaciones muy avanzadas y que incluso se podían programar, almacenando las instrucciones en tarjetas magnéticas y sacando los resultados en la impresora matricial asociada. MUY avanzado para el año 68. El primero de estos “milagros” fue la HP9100A, un aparato de “sólo” 20 kilos de peso y unos $4.900 (de la época) que daba el resultado de las operaciones introducidas en “pocos segundos”. Vamos, el no va más… La verdad es que cuando vi la foto me entraron unas lágrimillas de nostalgia porque yo he tenido máquinas de ese tipo. Concretamente tuve una de las “tataranietas”, la HP21 (más lágrimas de nostalgia), que fue algo así como la “superventas” de calculadoras personales en los 70 junto a algunas Casio.

Todos estos modelos tenían en común queee… ¡Acertaste! Funcionaban con RPN. Al principio te volvías un poco loco, sobre todo porque en el colegio no se veían estas cosas, pero con un poco de práctica le cogías el truco. Hoy en día, con la moda “retro” por todas partes, están proliferando aplicaciones para Android e iOS que instalan un emulador de la HP21 o cualquiera de sus hermanas en tu teléfono móvil y voilá! Ya tienes un dispositivo con RPN que puedes usar de forma cotidiana. Si tienes Android, te recomiendo que descargues la app HP21 scientific RPN calculator. Ocupa poco y funciona muy bien.

¿Dónde utilizarla? Pues si eres de esos, por ejemplo, que cuando va a la compra va sumando el precio de todo lo que va echando en el carro, te propongo que compares el proceso entre una calculadora normal y la HP21. Verás, como han concluido varios estudios, que la RPN no sólo es más sencilla, sino también mucho más rápida. En 3 o 4 compras tendrás el esquema de uso de una pila totalmente metido en la cabeza y la próxima vez que te enfrentes a un intéprete de R o una colección de Java entenderás mucho mejor el flujo de trabajo del programa. Lo mejor es cuando descubras lo fácil que es añadir a la cuenta cuatro paquetes del mismo producto y que no te haga falta una memoria temporal aparte para calcular el subtotal: 2 2 + 3 + 4 15 * +. ¿Comprendes?

Como poco, podrás fardar un poco de la app en el móvil. Para saber más, mira el artículo que encontrarás en el Museo de Calculadoras HP.