Traversée de commande d'une formule

Question

Dans les structures de données, j'obtiens la conversion dans l'ordre et les conversions de formules de pré-commande en arbres. Cependant, je ne suis pas très bon avec la post-commande.

Pour la formule donnée x y z + a b - c */-

je suis venu avec

    - 
       / \ 
       * /(divide) 
      /\ /\ 
       x + - c 
       /\ /\ 
       y z a b 

Pour la plupart, cela semble correspondre, à l'exception du * dans le sous-arbre gauche est le joker dans le pont. Dans la traversée d'ordre, le dernier caractère est le nœud supérieur de l'arbre, tout le reste se déconnecte. Maintenant, je prends les opérateurs/et * pour signifier qu'ils devraient être sur des noeuds opposés. Cependant, lors de la traversée d'un arbre, tout va bien sauf le *, puisque le sous-arbre gauche doit travailler jusqu'au noeud avant la racine, puis passer au sous-arbre droit.

Un coup de pouce dans la bonne direction est apprécié.

Answer 1

Go dans l'ordre. Tout d'abord, écrire la pile entière à nouveau:

x y z + a b - c */-

Maintenant, à partir de la gauche, recherchez le premier opérateur. Remplacer et les deux précédents opérandes, là dans la pile, avec un peu d'ordre peu:

x (y + z) ab - c */-

Continuons avec l'opérateur suivant:

x (y + z) (a - b) c */-

puis le suivant:

x (y + z) ((a - b) * c)/-

x ((y + z)/((a - b) * c)) -

x - ((y + z)/((a - b) * c))

Maintenant, pour en faire un arbre, il suffit de commencer au milieu (que vous savez déjà qu'il est le dernier élément dans la pile d'origine), et y suspendre des sous-expressions entre parenthèses, de l'extérieur vers l'intérieur.

Answer 2

En fait, il est plus facile d'écrire un programme qui analyse une expression post-commande que celui qui l'analyse dans l'ordre, car vous n'avez pas besoin de vérifier les priorités d'opérations. Essayez ceci: faites une pile, et ajoutez-y les opérandes comme vous les trouvez (de gauche à droite). Lorsque vous trouvez une opération, extrayez le nombre d'opérandes attendus de la pile et remettez un petit arbre. Lorsque vous le finissez, vous n'avez qu'un seul résultat dans la pile: le graphique final.

Ex:

x y z + -> x + 
      /\ 
       y z