Analizzatore di espressioni ricorsive utilizzando Java

Question

Sto per scrivere un valutatore di espressioni che esegue solo addizioni e sottrazioni. Ho un semplice algoritmo per farlo; ma, ho alcuni problemi di implementazione.

ho considerato un'espressione come (si tratta di una stringa)

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

Ecco il mio 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 

Il mio problema è l'analisi <expression1>, <operator> e <expression2> dall'espressione. Come lo posso fare?

Nota: non sto chiedendo un codice. Tutto ciò di cui ho bisogno è un'idea per farlo.

Grazie,

-Ali

Answer 1

Il mio problema è l'analisi <espressione1>, <operatore> e <espressione2> dal espressione

Non farlo, allora :) Quando si vede una parentesi di apertura, fare la tua chiamata ricorsiva all'espressione. Alla fine dell'espressione, o trovi un altro operatore (e quindi non sei alla fine dell'espressione dopotutto), o una parentesi quadra, nel qual caso torni dalla valutazione.

Answer 2

vorrei suggerire un approccio che ricorda più da vicino quello descritto in this vecchio, ma (a mio parere) relativa serie di articoli sul design del compilatore. Ho scoperto che l'approccio all'utilizzo di piccole funzioni/metodi che analizzano parti dell'espressione è estremamente efficace.

Questo approccio consente di scomporre il metodo di analisi in molti sottoprogrammi i cui nomi e l'ordine di esecuzione seguono da vicino lo EBNF che è possibile utilizzare per descrivere le espressioni da analizzare.

Answer 3

O si utilizza un generatore di parser come JavaCUP o ANTLR. Scrivi un BNF della tua espressione e genera un parser. Ecco una grammatica di esempio che potrebbe iniziare:

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

Un modo "hacky" di fare da soli potrebbe essere quella di cercare per la prima ) backtrack al ( sguardo più vicino alla libera espressione tra parentesi in mezzo, semplicemente dividere i simboli dell'operatore e valutare.

Answer 4

Forse creare regular expressions per espressione e operatore e quindi utilizzare la corrispondenza per identificare e uscire sul suo sito web.

Answer 5

Utilizzare StringTokenizer per dividere la stringa di input in parentesi, operatori e numeri, quindi scorrere i token, effettuare una chiamata ricorsiva per ogni open-parens ed uscire dal metodo per ogni parentesi chiusa.

So che non hai chiesto per il codice, ma questo funziona per input valido:

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; 
} 

Si avrebbe bisogno di una migliore gestione di input non valido, ma si ottiene l'idea ...

Answer 6

I raccomanderei di cambiare l'input infisso in postfix e quindi di valutarlo, piuttosto che ridurre l'espressione in senso infisso. Esistono già algoritmi ben definiti per questo e non viene fornito con i problemi di analisi delle parentesi multiple con nidificazione intrinseca.

Dai uno sguardo allo Shunting Yard Algorithm per convertire in postfix/RPN quindi valutarlo utilizzando uno stack utilizzando Postfix Operations. Questo è veloce (O (n)) e affidabile.

HTH