évaluateur d'expression récursive en utilisant Java

Question

Je vais écrire un évaluateur d'expression qui ne fait que l'addition et la soustraction. J'ai un algorithme simple à faire; mais, j'ai des problèmes de mise en œuvre.

Je considérais une expression comme (il est une chaîne)

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

Voici mon algorithme

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 

Mon problème est l'analyse <expression1>, <operator> et <expression2> de l'expression. Comment puis je faire ça?

Note: Je ne demande pas un code. Tout ce que je besoin est une idée de le faire.

Merci,

-Ali

Answer 1

  

Mon problème est parsing ,   Opérateur <> et de la   expression

Ne pas faire cela, alors :) Quand vous voyez un support d'ouverture, faites votre appel récursif à l'expression. A la fin de l'expresssion, que ce soit vous trouvez un autre opérateur (et donc vous n'êtes pas à la fin de l'expression après tout), ou un droit support, auquel cas vous revenez de l'évaluer.

Answer 2

Soit vous utilisez un générateur d'analyseurs tels que JavaCUP ou ANTLR . Rédiger une BNF de votre expression et générer un analyseur. Voici une grammaire exemple qui vous aider à démarrer:

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

Une façon de le faire vous-même serait de chercher la première ) backtrack à l'aspect le plus proche de ( « aki » à la parenthèse libre expression entre les deux, tout simplement divisé sur les symboles de l'opérateur et d'évaluer.

Answer 3

Je recommande de changer l'entrée infix dans Postfix, puis l'évaluer, plutôt que de réduire l'expression infix sage. Il existe déjà des algorithmes bien définis pour cela et il ne vient pas avec les imbrications multiples-parenthèses inhérentes d'analyse syntaxique des problèmes.

Jetez un oeil à la algorithme de triage pour convertir postfix / RPN puis évaluer à l'aide d'une pile en utilisant Postfix opérations . C'est rapide (O (n)) et fiable.

HTH

Answer 4

Utilisez un StringTokenizer pour diviser votre chaîne d'entrée en parenthèses, les opérateurs et les numéros, puis itérer sur vos jetons, en faisant un appel récursif pour tous ouverts parens, et en sortant de votre méthode pour chaque parenthèse fermante.

Je sais que vous n'avez pas demandé le code, mais cela fonctionne pour l'entrée valide:

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

Il aurait besoin d'une meilleure gestion des entrées invalides, mais vous voyez l'idée ...

Answer 5

Je suggère de prendre une approche qui ressemble plus à celui décrit dans cette ancienne, mais (en mon avis) de la série d'articles pertinents sur la conception du compilateur. Je trouve que l'approche de l'utilisation de petites fonctions / méthodes que les parties parse de l'expression très efficace.

Cette approche vous permet de décomposer votre méthode d'analyse en plusieurs sous-méthodes dont le nom et l'ordre d'exécution suit de près la EBNF vous pouvez utiliser pour décrire les expressions à analyser.

Answer 6

Peut-être créer des expressions régulières pour expression et opérateur et utiliser ensuite correspondant pour identifier et briser votre contenu.