Menu Close

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

     - 
    / \
   9   *
      / \
     2   4

Definiendo el tipo de dato Arbol por

   data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

la representación del árbol anterior es

   N (-) (H 9) (N (*) (H 2) (H 4))

Definir la función

   valor :: Arbol -> Int

tal que (valor a) es el valor de la expresión aritmética correspondiente al árbol a. Por ejemplo,

   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

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

Una solución de “Evaluación de árboles de expresiones aritméticas

  1. rebgongor
    data Arbol = H Int
               | N (Int -> Int -> Int) Arbol Arbol
     
    valor :: Arbol -> Int
    valor (H x) = x
    valor (N o i d) = o (valor i) (valor d)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.