domingo, octubre 10, 2010

Evaluador simple de funciones en java

Escribir un programa para evaluar una función que sea ingresada por el usuario como una cadena de caracteres es una labor que exige utilizar los pasos principales del proceso de compilación: análisis léxico, análisis sintáctico y análisis semántico.

En el programa en java que se transcribe a continuación, se define una clase llamada Expresion que puede ser incorporada fácilmente a cualquier otro programa, pues no requiere clases especiales diferentes a las ya existentes en la máquina virtual de java. Se requiere tan solo un uso reducido del paquete java.util.regex para el manejo de expresiones regulares, y del paquete java.lang.reflect para la invoación de métodos de la clase java.lang.Math como parte de la función ingresada por el usuario.

Los objetos de la clase Expresion se crean con una cadena que representa la función, la cual podría ser, por ejemplo "x^3-2*x^2+1", o incluso utilizar funciones matemáticas de la clase java.lang.Math que reciban un solo valor como parámetro, por lo que la función x*cos(x)^2 sería completamente válida.

import java.util.*;
import java.util.regex.*;
import java.lang.reflect.*;

public class Expresion {
    enum TipoToken  {   NUMERO, VARIABLE, FUNCION, ADD, SUB, MUL, DIV,
                        EXP, P_IZQ, P_DER, ERROR };
    class Token {
        TipoToken tipo;
        String    texto;
        Token(TipoToken ti, String te) { tipo=ti; texto=te;}
        Token(TipoToken ti) { tipo = ti; }
    }
    Queue<Token>    colaTokens;
    String          cadenaFuncion;
    double          variable;

    Expresion(String c) throws Exception {
        cadenaFuncion = c;
    }

    private void generarTokens() throws Exception {
        colaTokens = new LinkedList<Token>();
        StringBuffer entrada   = new StringBuffer(cadenaFuncion);
        Pattern pNumero = Pattern.compile("\\-?\\d+(\\.\\d+)?");
        Pattern pID     = Pattern.compile("\\p{Alpha}\\w+");
        while(entrada.length()>0) {
            Matcher      m  = pNumero.matcher(entrada);
            if(m.lookingAt()) {
                colaTokens.add(new Token(TipoToken.NUMERO,m.group()));
                entrada.delete(0, m.end());
                continue;
            }
            if(entrada.charAt(0) == 'x' || entrada.charAt(0) == 'X') {
                colaTokens.add(new Token(TipoToken.VARIABLE,"x"));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '+') {
                colaTokens.add(new Token(TipoToken.ADD));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '-') {
                colaTokens.add(new Token(TipoToken.SUB));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '*') {
                colaTokens.add(new Token(TipoToken.MUL));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '/') {
                colaTokens.add(new Token(TipoToken.DIV));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '(') {
                colaTokens.add(new Token(TipoToken.P_IZQ));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == ')') {
                colaTokens.add(new Token(TipoToken.P_DER));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '^') {
                colaTokens.add(new Token(TipoToken.EXP));
                entrada.deleteCharAt(0);
                continue;
            }
            m = pID.matcher(entrada);
            if(m.lookingAt()) {
                colaTokens.add(new Token(TipoToken.FUNCION, m.group()));
                entrada.delete(0, m.end());
                continue;
            }
            throw new Exception("Elemento no reconocido en la entrada: " 
                                 + entrada.charAt(0));
        }
    }

    private double evaluar(double x) throws Exception {
        generarTokens();
        variable = x;
        return expresion();
    }

    private double expresion() {
        double respuesta=termino();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case ADD:   colaTokens.remove();
                            respuesta+=termino();
                            continue;
                case SUB:   colaTokens.remove();
                            respuesta-=termino();
                            continue;
            }
            break;
        }
        return respuesta;
    }

    private double termino() {
        double respuesta=factor();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case MUL:   colaTokens.remove();
                            respuesta*=factor();
                            continue;
                case DIV:   colaTokens.remove();
                            respuesta/=factor();
                            continue;
                default:
            }
            break;
        }
        return respuesta;
    }

    private double factor() {
        double respuesta=valor();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case EXP:   colaTokens.remove();
                            respuesta=Math.pow(respuesta,valor());
                            continue;
            }
            break;
        }
        return respuesta;
    }

    private double valor() {
        Token token;
        try {
            double respuesta = 0;
            token     = colaTokens.poll();
            switch(token.tipo) {
                case P_IZQ:     respuesta = expresion();
                                leaToken(TipoToken.P_DER);
                                return respuesta;
                case NUMERO:    return Double.parseDouble(token.texto);
                case VARIABLE:  return variable;
                case FUNCION:   leaToken(TipoToken.P_IZQ);
                                double argumento=expresion();
                                leaToken(TipoToken.P_DER);
                                Method m = java.lang.Math.class.
                                           getMethod(token.texto, Double.TYPE);
                                return (Double) m.invoke(null, argumento);
            }
            return respuesta;
        }
        catch(Exception ex) {
            System.err.println("Error: "  + ex.getMessage());
            System.exit(0);
        }
        return 0;
    }

    private boolean leaToken(TipoToken t) {
        Token token = colaTokens.poll();
        if(token.tipo.equals(t)) {
            return true;
        }
        else {
            System.err.println("Error: elemento no permitido "  + token.texto );
            return false;
        }
    }

    public static void main(String[] args) throws Exception {
        String funcion = "x*cos(x)^2";
        Expresion  exp = new Expresion(funcion);
        for(int x=0; x<=10; x++  ) {
            System.out.println(exp.evaluar(x));
        }
    }
}

El método main es una muestra del uso que se le puede dar a esta clase. Es importante tener en cuenta que sólo acepta funciones definidas con la variable 'x' y que las funciones matemáticas de la clase java.lang.Math aceptadas son las que reciben un solo parametro como argumento. Sin embargo, es válido utilizar por ejemplo la fución "sin(cos(x^2+1))", ya que cada una de las funciones está recibiendo como argumento una función o expresión evaluable de un solo argumento.

10 comentarios:

  1. Anónimo6:38 a.m.

    Muy interesante, tiene una logica impecable

    lo voy a probar

    gracias por el aporte

    ResponderBorrar
  2. Anónimo3:48 p.m.

    no funciona cuando le ingreso por ejemplo la funcion x^2-1.no hace la diferencia.

    ResponderBorrar
  3. Anónimo3:50 p.m.

    luego de ingresar esa funcion cmo la de arriba aparece el mesaje Error: elemento no permitido -1

    ResponderBorrar
  4. Anónimo10:17 p.m.

    2*x^2-(1) debe ser asi para la resta

    ResponderBorrar
  5. Anónimo9:54 p.m.

    no la puedo compilar :( nose q mas tengo q agregarle una lcase principal??? porfis m urge

    ResponderBorrar
  6. Anónimo12:02 a.m.

    Encontre algo para el problema que decian sobre la resta... el problema esta en la expresion regular para los digitos en lugar de colocar
    "Pattern pNumero = Pattern.compile("\\-?\\d+(\\.\\d+)?");"
    se coloca
    "Pattern pNumero = Pattern.compile("\\d+(\\.\\d+)?");"
    asi se evita tener que colocar el numero que sigue al signo - entre parentesis asi todo el tiempo que se encuentre con un - va a asumir que es una resta y no un numero negativo ya que el numero negativo no esta definido en la lista de tokens

    ResponderBorrar
  7. Anónimo11:03 p.m.

    necesito que por favor alguien me explique este código mas detalladamente se lo agradecería de corazón..es para un trabajo en estructuras de datos..gracias

    ResponderBorrar
  8. Anónimo4:25 p.m.

    simplememnte perfecta... muchas gracias

    ResponderBorrar
  9. Excelente código mi hermano!!! tarea pasada

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...