Rekursive Ausdrucksauswerter Java unter Verwendung von

Question

Ich werde eine Ausdrucksauswertung schreiben, die nur Addition und Subtraktion der Fall ist. Ich habe einen einfachen Algorithmus zu tun, dass; aber ich habe einige Probleme bei der Umsetzung.

als ich einen Ausdruck wie (es ist ein String)

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

Hier ist mein Algorithmus

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 

Mein Problem ist das Parsen <expression1>, <operator> und <expression2> aus dem Ausdruck. Wie kann ich das machen?

Hinweis: Ich bin nicht für einen Code zu fragen. Alles was ich brauche ist eine Idee, das zu tun.

Danke,

-Ali

Answer 1

  

Mein Problem ist das Parsen ,   Operator <> und von der   Ausdruck

Sie das nicht tun, dann :) Wenn Sie eine öffnende Klammer zu sehen, machen Sie Ihren rekursiven Aufruf zum Ausdruck. Am Ende des express Sie entweder ein anderen Betreiber finden (und also sind Sie nicht am Ende des Ausdrucks, nachdem alle), oder eine rechte Klammer, in dem Fall, dass Sie von der Rückkehr zu bewerten.

Answer 2

Entweder Sie verwenden, um einen Parser-Generator wie JavaCUP oder ANTLR . Schreibe eine BNF des Ausdrucks und erzeugen einen Parser. Hier ist ein Beispiel Grammatik, die Sie erhalten würde gestartet:

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

A „Hacky“ Art und Weise, es zu tun selbst würde zum ersten ) Zurückverfolgungs zum nächsten ( Blick auf der Klammer freien Ausdruck suchen sein, zwischendurch, einfach auf dem Operator Symbole geteilt und zu bewerten.

Answer 3

würde ich empfehlen, die Infix Eingang in Postfix zu ändern und sie dann bewerten, anstatt die Verringerung der Ausdruck Infix-weise. Es gibt bereits gut definierten Algorithmen für dieses und es kommt nicht mit den inhärenten mehreren verschachtelten Klammern Parsen Probleme.

Werfen Sie einen Blick auf die Rangierbahnhof Algorithmus postfix zu konvertieren / RPN dann bewerten es mit einem Stapel Postfix Operationen verwenden. Das ist schnell (O (n)) und zuverlässig.

HTH

Answer 4

Verwenden Sie ein StringTokenizer teilen Sie Ihre Eingabe-String in Klammern, Operatoren und Zahlen, dann Iterierte über Ihre Token, einen rekursiven Aufruf für alle Open-Pars zu machen und Ihre Methode für jede Klammer zu verlassen.

Ich weiß, dass Sie nicht für Code nicht fragen, aber das funktioniert für gültige Eingabe:

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

Es müßte besser ungültiger Eingabe Handhabung, aber Sie bekommen die Idee ...

Answer 5

Ich würde einen Ansatz schlägt vor, dass ich enger an dem man in dieser alt beschrieben ähnelt, aber (in meiner Meinung nach) relevante Reihe von Artikeln über Compiler Design. Ich fand, dass der Ansatz der Verwendung von kleinen Funktionen / Methoden, die Parse-Teile des Ausdrucks sehr wirksam zu sein.

Dieser Ansatz ermöglicht es Ihnen, Ihre Analyseverfahren in viele Unter Methoden, deren Namen und Reihenfolge der Ausführung zu zersetzen lehnt sich eng an die EBNF könnten die Ausdrücke beschreiben analysiert werden.

Answer 6

reguläre Ausdrücke für Ausdruck und Operator und passende dann verwenden, um Ihre Inhalte zu identifizieren und auszubrechen.