La mayoría de las personas han aprendido a escribir expresiones aritméticas con los operadores entre los números ((2 + 2) / 5). Así es como la mayoría de las calculadoras te permiten insertar expresiones matemáticas y probablemente la notación con la que te enseñaron a contar en la escuela. Esta notación tiene la desventaja de que necesitas saber sobre la precedencia de los operadores: la multiplicación y la división son más importantes (tienen una precedencia más alta) que la suma y la resta.
Existe otra notación, llamada notación de prefijo o notación polaca, donde el operador va antes de los operandos. Bajo esta notación, (2 + 2) / 5 se convertiría en (/ (+ 2 2) 5). Si decidimos decir que + y / siempre toman dos argumentos, entonces (/ (+ 2 2) 5) puede escribirse simplemente como / + 2 2 5.
Sin embargo, nos centraremos en la notación polaca inversa (o simplemente RPN), que es lo opuesto a la notación de prefijo: el operador sigue a los operandos. El mismo ejemplo que el anterior en RPN se escribiría 2 2 + 5 /. Otras expresiones de ejemplo podrían ser 9 * 5 + 7 o 10 * 2 * (3 + 4) / 2 que se traducen a 9 5 * 7 + y 10 2 * 3 4 + * 2 /, respectivamente. Esta notación se utilizó mucho en los primeros modelos de calculadoras, ya que ocupaba poca memoria para su uso.
En primer lugar, puede ser bueno entender cómo leer expresiones RPN. Una forma de hacerlo es encontrar los operadores uno por uno y luego reagruparlos con sus operandos por aridad:
10 4 3 + 2 * -
10 (4 3 +) 2 * -
10 ((4 3 +) 2 *) -
(10 ((4 3 +) 2 *) -)
(10 (7 2 *) -)
(10 14 -)
-4
Sin embargo, en el contexto de una computadora o una calculadora, una forma más sencilla de hacerlo es hacer una pila de todos los operandos tal como los vemos. Tomando la expresión matemática 10 4 3 + 2 * -, el primer operando que vemos es 10. Lo agregamos a la pila. Luego está el 4, así que también lo colocamos en la parte superior de la pila. En tercer lugar, tenemos el 3; coloquemos también ese en la pila. Nuestra pila ahora debería verse así:
Una pila que muestra los valores [3 4 10]
El siguiente carácter a analizar es un +. Esa es una función de aridad 2. Para poder usarla, necesitaremos alimentarla con dos operandos, que se tomarán de la pila.
Entonces tomamos 3 y 4 de la pila, utilizados en la expresión de sufijo '3 4 +' y que devuelve 7 y ponemos este valor en la parte superior de la pila
La pila ahora es [7,10] y lo que queda de la expresión es 2 * -. Podemos tomar el 2 y colocarlo en la parte superior de la pila. Luego vemos *, que necesita dos operandos para funcionar. Nuevamente, los tomamos de la pila. Los operandos 2 y 7 tomados de la pila, utilizados en '7 2 *', que devuelve 14. Y colocamos 14 de nuevo en la parte superior de nuestra pila. Todo lo que queda es -, que también necesita dos operandos.
Dibuje los operandos 14 y 10 tomados de la pila en la operación '10 14 -' para el resultado '-4'
Y así tenemos nuestro resultado. Este enfoque basado en la pila es relativamente infalible y la poca cantidad de análisis que se necesita hacer antes de comenzar a calcular los resultados explica por qué era una buena idea que las calculadoras antiguas lo usaran.
Escribir esta solución en Erlang no es demasiado difícil una vez que hemos hecho las cosas complejas. Resulta que la parte difícil es averiguar qué pasos se deben realizar para obtener nuestro resultado final y eso es lo que acabamos de hacer. Creemos un archivo llamado calc.erl.
La primera parte de la que preocuparse es cómo vamos a representar una expresión matemática. Para simplificar las cosas, probablemente los ingresaremos como una cadena: "10 4 3 + 2 * -". Esta cadena tiene espacios en blanco, lo cual no es parte de nuestro proceso de resolución de problemas, pero es necesario para usar un tokenizador simple. Lo que sería utilizable entonces es una lista de términos de la forma ["10", "4", "3", "+", "2", "*", "-"] después de pasar por el tokenizador. Resulta que la función string:tokens/2 hace exactamente eso:
> string:tokens("10 4 3 + 2 * -", " ").
["10","4","3","+","2","*","-"]
Esa será una buena representación para nuestra expresión. La siguiente parte a definir es la pila. ¿Cómo vamos a hacer eso? Es posible que hayas notado que las listas de Erlang actúan de manera muy similar a una pila. El uso del operador cons (|) en [Head|Tail] se comporta de manera efectiva de la misma manera que colocar Head en la parte superior de una pila (Tail, en este caso). Usar una lista para una pila será suficiente.
Para leer la expresión, solo tenemos que hacer lo mismo que hicimos cuando resolvimos el problema a mano. Leer cada valor de la expresión, si es un número, colocarlo en la pila. Si es una función, extraer todos los valores que necesita de la pila y luego volver a colocar el resultado. Para generalizar, todo lo que necesitamos hacer es recorrer toda la expresión como un bucle solo una vez y acumular los resultados. ¡Suena como el trabajo perfecto para un fold!
Lo que necesitamos planificar es la función que lists:foldl/3 aplicará en cada operador y operando de la expresión. Esta función, como se ejecutará en un pliegue, necesitará tomar dos argumentos: el primero será el elemento de la expresión con el que se trabajará y el segundo será la pila.
Podemos comenzar a escribir nuestro código en el archivo calc.erl. Escribiremos la función responsable de todos los bucles y también de la eliminación de espacios en la expresión:
-module(calc).
-export([rpn/1]).
rpn(L) when is_list(L) ->
[Res] = lists:foldl(fun rpn/2, [], string:tokens(L, " ")),
Res.
Implementaremos rpn/2 teniendo en cuenta que, dado que cada operador y operando de la expresión termina colocándose en la parte superior de la pila, el resultado de la expresión resuelta estará en esa pila. Necesitamos sacar ese último valor de allí antes de devolvérselo al usuario. Es por eso que hacemos una coincidencia de patrones sobre [Res] y solo devolvemos Res.
Bien, ahora vamos a la parte más difícil. Nuestra función rpn/2 deberá manejar la pila para todos los valores que se le pasen. El encabezado de la función probablemente se verá como rpn(Op,Stack) y su valor de retorno como [NewVal|Stack]. Cuando obtenemos números regulares, la operación será:
rpn(X, Stack) -> [read(X)|Stack].
Aquí, read/1 es una función que convierte una cadena en un valor entero o de punto flotante. Lamentablemente, no hay una función incorporada para hacer esto en Erlang (solo una o la otra). La agregaremos nosotros mismos:
read(N) ->
case string:to_float(N) of
{error,no_float} -> list_to_integer(N);
{F,_} -> F
end.
Donde string:to_float/1 realiza la conversión de una cadena como "13.37" a su equivalente numérico. Sin embargo, si no hay forma de leer un valor de punto flotante, devuelve {error,no_float}. Cuando eso sucede, necesitamos llamar a list_to_integer/1 en su lugar.
Ahora volvamos a rpn/2. Todos los números que encontramos se agregan a la pila. Sin embargo, debido a que nuestro patrón coincide con cualquier cosa (consulte Coincidencia de patrones), los operadores también se colocarán en la pila. Para evitar esto, los colocaremos todos en cláusulas anteriores. La primera con la que intentaremos esto es la suma:
rpn("+", [N1,N2|S]) -> [N2+N1|S];
rpn(X, Stack) -> [read(X)|Stack].
Podemos ver que siempre que encontramos la cadena "+", tomamos dos números de la parte superior de la pila (N1,N2) y los sumamos antes de volver a colocar el resultado en esa pila. Esta es exactamente la misma lógica que aplicamos al resolver el problema a mano. Al probar el programa, podemos ver que funciona:
1> c(calc).
{ok,calc}
2> calc:rpn("3 5 +").
8
3> calc:rpn("7 3 + 5 +").
15
La función de prueba prueba todas las operaciones; si no se genera ninguna excepción, las pruebas se consideran exitosas. Las primeras cuatro pruebas verifican que las funciones aritméticas básicas funcionen correctamente. La quinta prueba especifica un comportamiento que aún no he explicado. La función try ... catch espera que se genere un error de coincidencia incorrecta porque la expresión no puede funcionar:
90 34 12 33 55 66 + * - +
90 (34 (12 (33 (55 66 +) *) -) +)
Al final de rpn/1, los valores -3947 y 90 se dejan en la pila porque no hay ningún operador que trabaje en el 90 que se queda colgado allí. Hay dos formas posibles de manejar este problema: ignorarlo y solo tomar el valor en la parte superior de la pila (que sería el último resultado calculado) o bloquearse porque la aritmética es incorrecta. Dado que la política de Erlang es dejar que se bloquee, es lo que se eligió aquí. La parte que realmente falla es la [Res] en rpn/1. Esta se asegura de que solo quede un elemento, el resultado, en la pila.
Las pocas pruebas que tienen la forma true = FunctionCall1 == FunctionCall2 están ahí porque no se puede tener una llamada de función en el lado izquierdo de =. Sigue funcionando como una aserción porque comparamos el resultado de la comparación con true.
También he añadido los casos de prueba para los operadores sum y prod para que puedan practicar su implementación. Si todas las pruebas son exitosas, deberían ver lo siguiente:
No hay comentarios.:
Publicar un comentario