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.

8 comentarios:

Anónimo dijo...

Muy interesante, tiene una logica impecable

lo voy a probar

gracias por el aporte

Anónimo dijo...

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

Anónimo dijo...

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

Anónimo dijo...

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

Anónimo dijo...

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

Anónimo dijo...

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

Anónimo dijo...

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

Anónimo dijo...

simplememnte perfecta... muchas gracias

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar