Notación polaca inversa
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
|
1 2 3 4 5 6 7 8 |
"" [] "20" [20] "20 4" [4, 20] "20 4 3" [3, 4, 20] "20 4 3 +" [7, 20] "20 4 3 + 2" [2, 7, 20] "20 4 3 + 2 *" [14, 20] "20 4 3 + 2 * -" [6] |
Definir la función
|
1 |
valor :: String -> Float |
tal que (valor cs) es el valor de la expresión RPN cs. Por ejemplo,
|
1 2 3 4 5 |
valor "4" == 4.0 valor "4 3 +" == 7.0 valor "4 3 + 2 *" == 14.0 valor "20 4 3 + 2 * -" == 6.0 valor "3 7 + 2 /" == 5.0 |
Soluciones
|
1 2 3 4 5 6 7 |
valor :: String -> Float valor = head . foldl aux [] . words where aux (x:y:ys) "+" = (x + y) : ys aux (x:y:ys) "-" = (y - x) : ys aux (x:y:ys) "*" = (x * y) : ys aux (x:y:ys) "/" = (y / x) : ys aux xs cs = read cs : xs |