Dev Faq
10
votes

Évaluateur d'expression récursif en utilisant Java

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

J'ai considéré une expression comme (c'est une chaîne) xxx

voici mon algorithme xxx < / Pré>

Mon problème est d'analyser , de l'expression. Comment puis je faire ça?

Remarque: Je ne demande pas de code. Tout ce dont j'ai besoin, c'est une idée de le faire.

merci,

-ali

1 commentaires

Si vous êtes intéressé par un exemple de travail d'un petit évaluateur de mathématiques Java écrit avec précision de cette façon, j'en ai une sur mon site Web: softwaremonkey.org/code/matheval

6 Réponses :

1
votes

Je suggérerais de prendre une approche qui ressemble plus de près celle décrite dans Ce vieux mais (dans Mon avis) série d'articles pertinents sur la conception du compilateur. J'ai constaté que l'approche d'utiliser de petites fonctions / méthodes qui analysent les parties de l'expression sont très efficaces.

Cette approche vous permet de décomposer votre méthode d'analyse dans de nombreuses sous-méthodes dont les noms et l'ordre d'exécution suivent de près le ebnf Vous pouvez utiliser pour décrire les expressions à analyser.

0 commentaires
7
votes

Mon problème est d'analyser , et de la Expression

Ne faites pas cela, alors :) Lorsque vous voyez un support d'ouverture, effectuez votre appel récursif à l'expression. À la fin de l'expression, vous trouvez un autre opérateur (et vous n'êtes donc pas à la fin de l'expression après tout), soit un support droit, auquel cas vous revenez de l'évaluation.

5 commentaires

Eh bien, faire un appel récursif à l'analyse d'expression1, il doit fondamentalement compter des parenthèses afin de dire où l'expression1 s'est terminée, mais sinon j'aime votre réponse.

Pas vraiment. La récursion fait le comptage pour vous. Si vous rencontrez un point) à un point où une expression pourrait se terminer, c'est la fin de cet appel récursif. C'est ainsi que des analyses de descente récursives fonctionnent ...

Ah, alors vous recursez sur la queue de la chaîne, même si c'est mal équilibré?

Je pense que si je vous comprends correctement. Si vous voyez un (, vous recueillez. Soit vous frappez la fin de l'entrée (auquel cas, erreur) ou que vous voyez un équilibre) et revenir de cette récursivité. Si vous voyez a) après revenir au niveau supérieur, c'est une erreur aussi. C'est ce que les générateurs d'analyseurs (de descendance récursive) produiront, mais il est éducatif à en mettre en œuvre vous-même. C'est pourquoi ils s'appellent une descente récursive, en fait!

Vous n'avez pas à faire de cela. Votre terme () et facteur () et prime () Les méthodes devraient simplement revenir si le prochain jeton n'est pas quelque chose qu'ils peuvent gérer. Ainsi, lorsque l'expression () revient dans le code qui l'a appelé à cause de "(", le prochain jeton devrait être ")". Si ce n'est pas le cas, il manque.

3
votes

Soit vous utilisez un générateur d'analyseur tel que Javacup ou antlr . Écrivez un BNF de votre expression et générez un analyseur. Voici une grammaire d'échantillon qui vous aiderait: 

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

3 commentaires

Je pense que vous avez quitté le numéro de votre grammaire.

C'est une grammaire ambiguë, car les parenthèses ne sont pas obligatoires.

Bon point. Et l'OP semblait avoir besoin de parenthèses alors je l'ai ajouté :-)

-2
votes

Peut-être créer peut-être Expressions régulières pour expression et l'opérateur puis utilisez la correspondance pour identifier et enfreindre votre contenu.

2 commentaires

Vous ne pouvez pas créer une expression régulière pour expression car cela implique des parenthèses bien équilibrées.

Ce n'est pas une langue régulière, il est libre de contexte et ne peut donc pas être analysé par des expressions régulières.

3
votes

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

Je sais que tu dis 'T Demander le code, mais cela fonctionne pour une entrée valide: xxx

Il aurait besoin de meilleure gestion d'une entrée non valide, mais vous obtenez l'idée ... < / p>

5 commentaires

Je n'ai pas compris pourquoi avez-vous utilisé GetNextToken () au lieu d'utiliser NextToken ()?

Il ne gère pas les parenthèses ou la priorité de l'opérateur correctement, et il ne sera jamais tant que vous ne l'introduisez pas, ou une pile d'opérande.

Les parenthèses sont traitées correctement et, étant donné que l'addition et la soustraction (seules 2 opérations nécessaires) ont la même précalence, il n'est pas nécessaire d'ajouter une logique supplémentaire pour cela. Si vous souhaitez que la multiplication et la division, alors oui, vous auriez besoin d'une pile d'opérande.

@Ecp: Mea Culpa - Je vois que vous avez raison à propos de la mauvaise manipulation de la parenthèse; Mon appel récursif inutile pour un ajout simple ou une soustraction était la messagement les choses là-bas ... c'est ce que je reçois pour essayer de pirater un code ensemble en 5 minutes: P J'ai corrigé le code pour supprimer cette récursive inutile.

@alicozgo getnextToken () est utilisé pour ignorer WhitSpace, bien que rétrospectivement aurait pu être ignoré par Eval () lui-même. Et vous avez raison, c'est essentiellement la même solution que Paul a suggéré.

3
votes

Je recommanderais de modifier la saisie de l'infixe en postfix, puis de l'évaluer, plutôt que de réduire l'expression infixe. Il existe déjà des algorithmes bien définis pour cela et cela ne vient pas avec les problèmes inhérents à plusieurs parenthèses.

Jetez un coup d'œil au Algorithme de coureurs de courage pour convertir en postfix / RPN puis évaluer Il utilise une pile utilisant Opérations postfix . Ceci est rapide (O (n)) et fiable.

htth

1 commentaires

Celui-ci est facile et simple. +1.

Articles qui pourrait vous intéresser :

Comment envoyer une liste vide à la clause IN
Code de réponse 403 inattendu lors de la récupération des données des API
Impossible de trouver la classe UnityPlayerActivity dans com.unity3d.player
Comment définir un tableau dans jsonobject