Ricorsivo analizzatore di espressioni utilizzando Java

Question

Ho intenzione di scrivere un analizzatore di espressioni che fa solo addizione e sottrazione. Ho un algoritmo semplice per farlo; ma, ho alcuni problemi di attuazione.

I considerata un'espressione come (è 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 quello che serve è un'idea per farlo.

Grazie,

-Ali

Answer 1

  

Il mio problema è l'analisi ,    e dal   espressione

Non farlo, allora :) Quando si vede una parentesi di apertura, fare la chiamata ricorsiva di espressione. Alla fine del expresssion, sia a trovare un altro operatore (e quindi non sei alla fine dell'espressione dopo tutto), o un diritto-staffa, nel qual caso si torna dalla valutare.

Answer 2

O si utilizza un generatore di parser come JavaCUP o ANTLR . Scrivi una BNF della vostra espressione e generare 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 look ( più vicina alla libera espressione tra parentesi in mezzo, semplicemente diviso sui simboli degli operatori e valutare.

Answer 3

consiglierei modifica dell'ingresso infissa nel suffisso e quindi valutare che, invece di ridurre l'espressione infissa-saggio. Esistono già algoritmi ben definiti per questo e non vengono con gli inerenti multiple-nested-parentesi parsing problemi.

Date un'occhiata al href="http://en.wikipedia.org/wiki/Shunting-yard_algorithm" rel="nofollow"> Scalo di smistamento Algoritmo per convertire in postfix / RPN poi valutare utilizzando uno stack utilizzando Postfix Operations . Questo è veloce (O (n)) e affidabile.

HTH

Answer 4

Usa uno StringTokenizer per dividere la stringa di input in parentesi, gli operatori ed i numeri, poi iterare sopra i vostri gettoni, facendo una chiamata ricorsiva per ogni open-parentesi, e la chiusura del 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 5

Vorrei suggerire un approccio che più da vicino assomiglia a quella descritta in questo vecchio ma (in mio parere) serie di importanti articoli sulla progettazione del compilatore. Ho trovato che l'approccio di utilizzare piccole funzioni / metodi che le parti parsing dell'espressione di essere altamente efficace.

Questo approccio consente di scomporre il tuo metodo di analisi in molti sotto-metodi i cui nomi e l'ordine di esecuzione segue da vicino la EBNF si potrebbe usare per descrivere le espressioni da analizzare.

Answer 6

espressioni regolari per espressione e operatore e quindi utilizzare la corrispondenza per identificare e uscire sul suo sito web.