8
votes

Construire un arbre d'expression binaire

Quelqu'un pourrait-il expliquer comment construire un arbre d'expression binaire.

Par exemple, j'ai une chaîne 2 * (1+ (2 * 1)); code> Comment convertir cela en une expression binaire Arbre. P>

 *
 | \
 |  \
 2  +
    |\
    1 *
      |\
      2 1

algorithm expression-trees

1 commentaires

Vous pouvez implémenter une solution à l'aide de l'algorithme de la cour de la cour. Voici quelques détails sur WikiPiedia: << a href = "https://fr.wikipedia.org/wiki/shunting-yard_algorithm" rel = "Nofollow Noreferrer"> en.wikipedia.org/wiki/shunting-yard_algorithm >. Cet algo a été inventé par Edsger Dijkstra, c'est une très belle alternative. Si vous avez besoin de détails, je peux poster un exemple de code que j'ai écrit dans C # il y a quelque temps mais je suppose que le lien Wikipedia est plus que suffisant.

4 Réponses :

0
votes

Convertissez l'expression en notation préfixe ou postfix. De là, il devrait être assez simple. Les algorithmes sont mentionnés dans les liens Wiki suivants.

http://en.wikipedia.org/wiki/polish_notation

http://fr.wikipedia.org/wiki/Reverse_polish_notation

0 commentaires

2
votes

Vous devrez:

Définissez une grammaire qui décrit votre langue
Écrivez un analyseur lexical qui lit les jetons de votre chaîne
Écris un analyseur qui construit un arbre des jetons
Par exemple, jetez un coup d'œil à cette approche: http://en.wikipedia.org/wiki/ RECURSIVE_DESCENT_PARSER
Il y a d'autres

1 commentaires

Ceci est probablement surchargé pour ce qui est une affectation plutôt simple à montrer visuellement comment les expressions sont analysées.

11
votes

Convertir Infix en Postfix ou Prefix

L'entrée Postfix est: A B + C D E + ** **

Considérez le premier caractère s'il n'est pas symbole, créez le nœud l'ajout à la pile
Si le caractère est un symbole, créez un nœud avec des éléments pop symboliques et ajouter à gauche et à droite du symbole
poussez le nœud symbole dans la pile.
Répétez les répétitions 1, 2 et 3 jusqu'à ce que Itérateur n'ait plus d'éléments
implémentation Java xxx
Plus d'infos: http://fr.wikipedia.org/wiki/binary_expression_tree

1 commentaires

Ici symbol = opérateur

0
votes

Il peut être divisé en deux étapes:

Calculez la valeur de priorité pour chaque jeton.
Par exemple: '+': 1, 'X': 2, Numéro: Inf, '(': Ajoutez 10 à Base, ')': Soustrait 10 de la base)
construire arbre cartésien en fonction de la priorité en utilisant une pile (environ 5 lignes de code)
Vous pouvez le faire en une seule numérisation.

0 commentaires