Comment analyser et construire un arbre à partir d'expressions arithmétiques en Java ?

Analyser une expression arithmétique et construire un arbre à partir de celle-ci en Java

Introduction

Analyser des expressions arithmétiques et construire des arbres équivalents est une tâche essentielle dans la conception du compilateur et le traitement du langage. Cet article montrera comment analyser une expression arithmétique et créer une représentation arborescente en Java.

Analyse de l'expression

Pour analyser l'expression, nous pouvons utiliser une pile- algorithme basé sur. Pendant que nous parcourons l'expression :

• Poussez les parenthèses ouvrantes sur la pile.
• Poussez les nombres et les opérateurs sur la pile.
• En rencontrant une parenthèse fermante, évaluez la sous-arbre en faisant éclater la pile jusqu'à atteindre la parenthèse ouvrante correspondante, puis poussez le résultat sur la pile.

Construire l'arbre

Une fois l'expression analysée, nous pouvons construire les nœuds de l'arbre à partir de la pile :

• Nœuds feuilles : Les entiers deviennent des nœuds LeafInt.
• Nœuds d'opérateur : Les opérateurs deviennent nœuds avec des classes PlusOp, MinusOp, MultOp ou DivOp, et leurs enfants sont des pops de la pile.

Exemple

Considérez l'expression (5 2) *7 :

<code class="java">Stack<Node> stack = new Stack<>();
stack.push(new LeafInt(5));
stack.push(new PlusOp());
stack.push(new LeafInt(2));
stack.push(new MultOp());
stack.push(new LeafInt(7));
while (stack.size() > 1) {
  Node right = stack.pop();
  Operator op = (Operator) stack.pop();
  Node left = stack.pop();
  stack.push(new OpNode(op, left, right));
}</code>

L'arbre résultant aurait la structure suivante :

    *
   / \
  +   7
 / \
5   2

Gestion des nombres négatifs et des parenthèses

Pour gérer les nombres négatifs nombres, représentez-les par 5 (-2) au lieu de 5-2. Les signes négatifs ont toujours une priorité unaire. De même, les parenthèses forcent l'ordre des opérations.

Validation

Pour garantir l'exactitude, validez l'expression en vérifiant :

• Les parenthèses ouvrantes ont correspondant aux parenthèses fermantes.
• Chaque opérateur a le nombre correct d'opérandes.

Conclusion

En utilisant un algorithme basé sur la pile, il est simple pour analyser des expressions arithmétiques et construire leurs représentations arborescentes équivalentes. Cette approche fournit une base fiable pour une analyse et une manipulation plus approfondies des expressions arithmétiques en Java.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!