Prueba Estructura de Datos - Mi versión de la prueba.

Bien niños, para aquellos que sobrevivieron, los que ya recuperaron la conciencia y los que ya hayan salido de la transfusión de sangre les comparto mi versión de la primera prueba de ED. Lamento tener que decirles que las primeras 3 preguntas eran un regalo, solo la cuarta era un marciano.

1.- Recibir un string con una expresión aritmética y retornar su valor entero.

Estaba resuelta en la entrada anterior. Sólo se necesitaba la primera función de la clase. Recuerden que el profe sólo pide algoritmos (como se resuelve un problema) no programas completamente funcionales.

public static int evaluaEcuacion(String strEcuacion)
{
  if(blnIsNum(strEcuacion))
   return Integer.parseInt(strEcuacion);
   
  strEcuacion = quitaParentesisExteriores(strEcuacion);
   
  String strEcIzq = obtenerPrimerMiembro(strEcuacion);
  char   strOp    = strEcuacion.charAt(strEcIzq.length());
  String strEcDer = strEcuacion.substring(strEcIzq.length()+1);
   
  return opera(strOp, evaluaEcuacion(strEcIzq), evaluaEcuacion(strEcDer));
 }

2.- Convertir un entero a string hexadecimal.

Este problema estaba resuelto en el dummyMath.java que envié a la carpeta del curso en google docs, y también estaba en esta entrada del blog.

public static String hexadecimal(int n)
{
 if (n==0) return "";

 int digHex = n%16; 

 switch (digHex)
 {
  case 10: return hexadecimal(n/16)+"A"; 
  case 11: return hexadecimal(n/16)+"B"; 
  case 12: return hexadecimal(n/16)+"C"; 
  case 13: return hexadecimal(n/16)+"D"; 
  case 14: return hexadecimal(n/16)+"E"; 
  case 15: return hexadecimal(n/16)+"F"; 
  default: return hexadecimal(n/16)+Integer.toString(digHex);
 }
}

3.-Insertar un elemento en forma ordenada en una lista circular.

Este era igual al que el profe nos dió en clases pero con una ligera modificación.

public Lista insertarOrdenado(Lista L, int dato)
{
 if (l==null)
 {//Esta es la que había que modificar
  Lista nueva == new Lista(dato);
  nueva.siguiente = nueva;
  return nueva;
 }

 if (dato < l.dato)
 {
  Lista nueva == new Lista(dato);
  nueva.siguiente = this;
  return nueva;
 }

 l.siguiente = insertarOrdenado(l.siguiente, dato);
 return l;
}

4.- Buscar a un usuario en una lista y retornar cuanto tiempo ha hecho uso del sistema.

Este sí que era un marciano. Vamos a definir varios supuestos para simplificar el algoritmo.

1. La lista es de objetos que tienen los campos descritos en el encabezado de la pregunta, por lo que podemos acceder a ellos así l.accion, l.usuario, l.horario... bla bla bla.
2. El campo l.horario es un objeto que posee un método que convierte la hora en número decimal.
3. La función va a devolver un  double (Es decir puede devolver 3,5 si el usuario estuvo conectado 3 horas y media por ejemplo).
4. Que existe una función llamda diffHora(double salida, double entrada)  que se encarga de convertir a número, sacar la diferencia, ver si se pasó de día... etc.

public double tiempoDeConex(Strng usuario, Lista L, double hora)
{//Si llegamos al final de la lista retornamos 0.
 if (L==null)
  return (double) 0;

 //Si encontramos al usuario preguntamos cual es la acción
 //Si la acción es "Sale" devolvemos la diferencia entre la hora
 //que hay en el elmento de la lista y la que viene como parámetro
 //(Ojo, la hora del parametro viene de la acción "Entra".
 if (L.usuario == usuario)
 {
  if (L.accion == "Sale")
  {// pido el resultado de la recursión siguiente y lo devuelvo
   // sumado con el resultado de la recursión actual
   double horaAux = tiempoDeConex(usuario, L.siguiente, 0);
   return horaAux + difHora(l.horario.toDouble(), hora);
  }
  //Si la accion es "Entra" envío la hora de entrada
  //a la recursión siguiente 
  return tiempoDeConex(usuario, L.siguiente, l.horario.toDouble());
 }
 //Y si no he encontrado al usuario envío todos los datos
 //que vienen en los parámetros al dato siguiente.
 return tiempoDeConex(usuario, L.siguiente, hora);
}

No sé si está bueno. De hecho parece que tampoco lo contesté así en la prueba pero bue... si alguien le encuentra la falla que lo diga y así vamos mejorando esto.

Un abrazo a todos.

Recursividad - Ejercicios resueltos 101

Actualización 10-10-2012:

Todo puede mejorar. Ahora puede resolver cualquier sobrecarga de paréntesis y resolver números signados. Tuve que agregar una función recursiva más (cierreParentesis()), esta vez era necesaria, para que discriminara cual paréntesis cerraba a cada cual y así saber si el primero y el último de la expresión se cerraban entre sí.

Fin actualización.

Qué tal chicos.

Para este viernes el profe nos hizo un regalito para la prueba.

Como el regalo es para todos les comparto mi versión.
Este programa funciona con las siguientes restricciones:

• No se pueden poner números signados entre las operaciones (ej: -13+-51) solo operaciones entre números naturales. (deprecado)
• Los paréntesis siempre deben estar equilibrados.
• Entre los paréntesis sólo puede haber operaciones y no números solos o signados (ej: "(+58)").(deprecado)
• No sirve para elementos con sobrecarga de parentesis, ej: (((9+8))).(deprecado)

Saquen sus versiones modifíquenlo, mejórenlo y nos vemos en la prueba este viernes.

Que nos vaya bien:

6.- Escriba un programa en Java que reciba un string que contenga una expresión aritmética y que retorne el valor de la evaluación.
Ej: "((5+1)*(7-6))" = 6.

Solución:

public class evaluaEcuacionString
{
 public static int evaluaEcuacion(String strEcuacion)
 {
  strEcuacion = quitaParentesisExteriores(strEcuacion);
  
  if(blnIsNum(strEcuacion))
   return Integer.parseInt(strEcuacion);
    
  String strEcIzq = obtenerPrimerMiembro(strEcuacion);
  char   chrOp    = strEcuacion.charAt(strEcIzq.length());
  String strEcDer = strEcuacion.substring(strEcIzq.length()+1);
  
  return opera(chrOp, evaluaEcuacion(strEcIzq), evaluaEcuacion(strEcDer));
 }
 
 private static int opera(char op, int a, int b)
 {
  switch (op)
  {
  case '+': return a + b;
  case '-': return a - b;
  case '*': return a * b;
  default : return (int) a / b;
  }
 }
 
 private static String quitaParentesisExteriores(String ecu)
 {
  if(ecu.charAt(0) =='(')
   if(ecu.charAt(ecu.length()-1) ==')')
    if(entreParentesis(ecu))
     return quitaParentesisExteriores(ecu.substring(1, ecu.length()-1));
   
        return ecu;         
    }
 
 private static boolean entreParentesis(String ecu)
 {
  return (cierreParentesis(ecu,1) == ecu.length()-1);  
 }
 
 private static int cierreParentesis(String ecu, int pos)
 {
  int i = pos;
  int cerrado=-1;
  
  while (i <= ecu.length()-1)
  {
   //if(i < ecu.length())
    if(ecu.charAt(i)==')')
     return i;
   
   if(ecu.charAt(i)=='(')
   {
    cerrado = cierreParentesis(ecu, i+1);
    i = cerrado;
   }
   
   i++;
   
   
   
  }
  return cerrado;// return i==ecu.length();
 }
 
 
 private static String obtenerPrimerMiembro(String ecu)
 {
  String miembro="";
  
  if(ecu.charAt(0)=='(')
  { 
   int equilibrio = 0;
   int i=0;
   do
   {
    char elem = ecu.charAt(i);
    miembro+= elem;
    if(elem == '(')
     equilibrio++;
    
    if(elem == ')')
     equilibrio--;
    
    i++;
    
   }while (equilibrio != 0);
  }
  else
  {
   miembro+=ecu.charAt(0);
   
   for(int i=1; Character.isDigit(ecu.charAt(i)); i++)
    miembro+=ecu.charAt(i);
  }
  return miembro;
 }
 
 private static boolean blnIsNum(String s)
 {
  //retorna true si el string representa un entero
  //con o sin signo
  
  int primerChar = 0;
  if(s.charAt(0)=='+' || s.charAt(0)=='-')
   primerChar=1;
   
  for(int i=primerChar; i< s.length(); i++)
   if(!Character.isDigit(s.charAt(i)))
    return false;
  
  return true;
 }
 
 
 public static void main(String[] args)
 {
  //Modifiquen el string para probarlo
  // ;-)
  
  System.out.println(evaluaEcuacion("(((5*3)/(2-1)))+(((5/3)+8)-60)"));
 }

}