Evaluador de expresiones recursivas usando Java

Question

Voy a escribir un evaluador de expresiones que solo hace sumas y restas. Tengo un algoritmo simple para hacer eso; pero, tengo algunos problemas de implementación.

me considera una expresión como (se trata de una cadena)

"(" <expression1> <operator> <expression2> ")" 

Aquí está mi algoritmo

String evaluate(String expression) 

    if expression is digit 
     return expression 

    else if expression is "(" <expression1> <operator> <expression2> ")" 
     cut the brackets out of it 
     expression1 = evaluate(<expression1>) 
     operator = <operator> 
     expression2 = evaluate(<expression2>) 

    if operator is + 
     expression1 + expression2 

    else if operator is - 
     expression1 - expression2 

Mi problema es analizar <expression1>, <operator> y <expression2> de la expresión. ¿Cómo puedo hacer eso?

Nota: No estoy pidiendo un código. Todo lo que necesito es una idea para hacer eso.

Gracias,

-Ali

Answer 1

Mi problema es analizar < expresión 1 >, <operador> y < expresión 2 > de la expresión

No hacer eso, entonces :) Cuando vea un paréntesis de apertura, hacer su llamada recursiva a la expresión. Al final de la expresión, o bien encuentra otro operador (y, por lo tanto, no está al final de la expresión), o un corchete de la derecha, en cuyo caso regresa de la evaluación.

Answer 2

que sugeriría un enfoque que se asemeja más a la descrita en this viejo, pero (en mi opinión) correspondiente serie de artículos sobre el diseño de compiladores. Encontré que el enfoque de usar pequeñas funciones/métodos que analizan partes de la expresión es altamente efectivo.

Este enfoque le permite descomponer su método de análisis en muchos submétodos cuyos nombres y el orden de ejecución sigue de cerca al EBNF que puede utilizar para describir las expresiones que se analizarán.

Answer 3

O utiliza un generador de analizador como JavaCUP o ANTLR. Escribe un BNF de tu expresión y genera un analizador. Aquí está una gramática modelo que empezar:

Expression ::= Digit 
      | LeftBracket Expression Plus Expression RightBracket 
      | LeftBracket Expression Minus Expression RightBracket 
      | LeftBracket Expression RightBracket 

Una forma "hacky" de hacerlo usted mismo habría que buscar la primera ) dar marcha atrás a la ( mirada más cercana a la libre expresión entre paréntesis en el medio, simplemente dividir en los símbolos del operador y evaluar.

Answer 4

Tal vez crear regular expressions de expresión y operador de juego y luego utilizar para identificar y explotar su contenido.

Answer 5

Use un StringTokenizer para dividir su cadena de entrada en paréntesis, operadores y números, luego itere sobre sus tokens, realice una llamada recursiva para cada par abierto y salga de su método para cada paréntesis cercano.

Sé que no pidió código, pero esto funciona para entrada válida:

public static int eval(String expr) { 
    StringTokenizer st = new StringTokenizer(expr, "()+- ", true); 
    return eval(st); 
} 

private static int eval(StringTokenizer st) { 
    int result = 0; 
    String tok; 
    boolean addition = true; 
    while ((tok = getNextToken(st)) != null) { 
     if (")".equals(tok)) 
      return result; 
     else if ("(".equals(tok)) 
      result = eval(st); 
     else if ("+".equals(tok)) 
      addition = true; 
     else if ("-".equals(tok)) 
      addition = false; 
     else if (addition) 
      result += Integer.parseInt(tok); 
     else 
      result -= Integer.parseInt(tok); 
    } 
    return result; 
} 

private static String getNextToken(StringTokenizer st) { 
    while (st.hasMoreTokens()) { 
     String tok = st.nextToken().trim(); 
     if (tok.length() > 0) 
      return tok; 
    } 
    return null; 
} 

Se necesitaría un mejor manejo de la entrada no válida, pero se entiende la idea ...

Answer 6

I recomendaría cambiar la entrada de infijo en postfix y luego evaluarla, en lugar de reducir la expresión en infijo. Ya existen algoritmos bien definidos para esto y no vienen con los problemas inherentes de análisis de paréntesis entre paréntesis múltiples.

Eche un vistazo a Shunting Yard Algorithm para convertir a postfix/RPN y luego evalúe usando una pila usando Postfix Operations. Esto es rápido (O (n)) y confiable.

HTH