Comment analyser et construire un arbre à partir d'une expression arithmétique en Java ?

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

Cet article approfondit la tâche d'analyse d'une expression arithmétique et de construction d'un structure de données arborescente correspondante en Java. L'objectif est de traiter une expression comme "(5 2)*7" dans un arbre ressemblant à la structure de l'expression.

Approche : Utiliser une pile

Pour analyser le expression, une pile peut être utilisée. L'approche implique le traitement itératif des jetons de l'expression :

• Si une parenthèse ouvrante "(" est rencontrée, elle est poussée sur la pile.
• Si un nombre (opérande) est rencontré , il est stocké en tant que nœud feuille et poussé sur la pile.

• Si un opérateur ( , -, *, /) est rencontré :

  • Sa priorité est comparée à l'opérateur supérieur de la pile.
  • Si la priorité est inférieure ou égale, l'expression est évaluée jusqu'au "(" précédent ou au début de l'expression.
  • Le résultat de l'opérateur l'évaluation est poussée sur la pile.

Exemple : analyse de "(5 2)*7"

Envisagez d'analyser l'expression " (5 2)*7":

• "(" est poussé sur la pile.
• "5" est poussé sur la pile en tant que nœud feuille.
• " " est poussé sur la pile.
• "2" est poussé sur la pile en tant que nœud feuille.

• ")" est rencontré, donc l'expression "5 2" est évalué :

  • Les nœuds feuilles "5" et "2" sont extraits de la pile.
  • Un nouveau nœud d'ajout " " est créé, avec les deux nœuds feuilles comme enfants.
  • Le nœud d'addition est poussé sur la pile.
• "*" est poussé sur la pile.
• "7" est poussé sur la pile en tant que nœud feuille.

• "eof" (fin de l'expression) est rencontré, donc l'expression "(node) 7" est évaluée :

  • Le nœud de multiplication "(*node)" et le nœud feuille "7" sont retirés de la pile.
  • Un nouveau nœud de multiplication "*" est créé et placé sur la pile.

L'arborescence finale récupérée de la pile s'alignera sur l'expression d'origine :

    *
   / \
  +   7
 / \
5   2

Conclusion

Utilisation une pile pour analyser les expressions arithmétiques permet une construction efficace de structures de données arborescentes représentant ces expressions. Cette approche permet d'effectuer des opérations et des analyses supplémentaires sur les arbres analysés.

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!