La conversion d'une expression infix (entre parenthèses) dans un arbre binaire

Dans le cadre d'une application Java, je dois prendre une entrée une expression arithmétique et de le stocker dans un arbre binaire.

J'ai fait tout le nécessaire pour la cession sauf pour la partie où j'ai lu dans la chaîne de l'expression et de la stocker dans l'arbre binaire.

J'ai créé une catégorie appelée BinaryTree. Son seul champ est un treenode appelé racine. Cette treenode est défini comme un innerclass dans BinaryTree. Il dispose de 3 champs, un générique champ de données, et de deux enfants (gauche et droite) qui sont de type BinaryTree.

Je vais avoir un moment très difficile de définir un algorithme pour la lecture dans une expression comme

(5*(2+3)^3)/2

et de les stocker dans un arbre comme ce

             /
        ^          2
    *       3
  5   +
     2  3

N'importe qui peut aider avec l'algorithme?

Essayez une simple équation de la chaîne: 1+2. Lorsque vous obtenez ce que, n': 1+2*3. Encore plus complexe: 1*2+3. Enfin: (1+2)*3
Voulez-vous une explication pour l'algo?

OriginalL'auteur HesNotTheStig | 2012-04-24

  1. 6

    Prendre un coup d'oeil à la shunting-yard algorithme. De Wikipedia:

    En informatique, la shunting-yard algorithme est une méthode pour l'analyse des expressions mathématiques spécifié dans la notation infixe. Il peut être utilisé pour produire le résultat en notation polonaise Inversée (RPN) ou comme un arbre de syntaxe abstraite (AST). L'algorithme a été inventé par Edsger Dijkstra et a nommé la "manœuvre de triage" de l'algorithme, car son fonctionnement ressemble à celui d'un chemin de fer de manœuvre de triage. Dijkstra a le premier décrit la Manœuvre de Triage de l'Algorithme dans Mathematisch Centrum rapport de M. 34/61.

    OriginalL'auteur NPE

  2. 3

    Voici quelques Le code C++ pour créer une expression binaire de l'arbre qui utilise deux piles, l'une pour les opérateurs et un autre pour les opérandes. Finalement, l'opérande de la pile contient un seul élément, la complète expression binaire de l'arbre.

    OriginalL'auteur Kurt Krueckeberg