Evaluación de árboles de expresiones aritméticas
Las expresiones aritméticas se pueden representar como árboles con números en las hojas y operaciones en los nodos. Por ejemplo, la expresión «9-2*4» se puede representar por el árbol
|
1 2 3 4 5 |
- / \ 9 * / \ 2 4 |
Definiendo el tipo de dato Arbol por
|
1 |
data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol |
la representación del árbol anterior es
|
1 |
N (-) (H 9) (N (*) (H 2) (H 4)) |
Definir la función
|
1 |
valor :: Arbol -> Int |
tal que (valor a) es el valor de la expresión aritmética correspondiente al árbol a. Por ejemplo,
|
1 2 3 4 |
valor (N (-) (H 9) (N (*) (H 2) (H 4))) == 1 valor (N (+) (H 9) (N (*) (H 2) (H 4))) == 17 valor (N (+) (H 9) (N (div) (H 4) (H 2))) == 11 valor (N (+) (H 9) (N (max) (H 4) (H 2))) == 13 |
Soluciones
|
1 2 3 4 5 |
data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol valor :: Arbol -> Int valor (H x) = x valor (N f i d) = f (valor i) (valor d) |
Pensamiento
En cierto modo, las matemáticas no son el arte de responder preguntas matemáticas, es el arte de hacer las preguntas correctas, las preguntas que te dan una idea, las que te guían en direcciones interesantes, las que se conectan con muchas otras preguntas interesantes, las que tienen hermosas respuestas. ~ Gregory Chaitin
Un comentario