Problema - Decision Tree

Este problema apareció en el Round 1B del CodeJam 2009. El link del problema:
http://code.google.com/codejam/contest/dashboard?c=186264#.

El problema es relativamente sencillo. En resumen lo que se tiene que hacer es hacer una función que transforme el árbol del formato texto (String) a una estructura de datos determinada y luego otra que permita el procesamiento.

Solo hay que hacer lo que dice el enunciado, pero la programación se puede complicar si no se tienen las estructuras de datos adecuadas. Además utilizando la recursividad simplifica las funciones.

Mi estructura de datos:

    static class Nodo{
        String feature;
        double p;
        Nodo left;
        Nodo right;
    }

Mi enfoque fue usar dos funciones, una de interpretación y otra de ejecución:

  double ejecutar(HashSet<String> features, Nodo raiz)
  Nodo interpret(String x)

La función interpret lo que hace es, a partir del String tree generar un nodo. El String 'tree' tiene la forma"0.54 fast (...) (...)" ó "0.36".

• Si se corresponde al 1er caso lo que hice fue identificar los strings que se encuentran dentro de cada uno de estos paréntesis teniendo como nodo resultante algo asi: Nodo("fast",0.54,interpret("..."),interpret("..."))
• El 2do caso es mas simple. El nodo resultante seria asi: Nodo(null,0.36,null,null)

Ahora la función ejecutar: (en java)

 private static double ejecutar(HashSet<String> features, Nodo raiz){
      if(raiz.left == null)
          return raiz.p;
      if(features.contains(raiz.feature))
          return raiz.p * ejecutar(features,raiz.left);        
      return raiz.p * ejecutar(features,raiz.right);
  }

Esta función tiene 3 casos. Si el nodo es un nodo final, sin hijos, devuelve la probabilidad p del nodo. En caso no sea final y la 'feature' del nodo este contenida dentro de las 'features' del animal entonces devuelve la probabilidad p multiplicada por la probablidad del hijo izquierdo. Caso contrario va por el lado derecho.

El código del programa lo pueden ver en el mismo codejam. Mi código (en java) lo pueden ver con el usuario 'zaratov'.