Arbres binaires, construire un arbre basé sur le précommande

Question

construire un arbre étant donné qu'il est en stock est assez facile. Mais, disons que vous êtes supposé construire un arbre basé sur sa précommande (+ + y z + * x y z par exemple).

Il est facile de voir que + est la racine, et comment continuer dans le sous-arbre gauche à partir de là. Mais .. comment savez-vous quand vous êtes censé "passer" au sous-arbre de droite?

Answer 1

Habituellement, enordre est considéré comme le cas difficile.

Pour la précommande, vous aurez juste une grammaire comme celle-ci.

expr ::= operator expr expr | var 

Un opérateur est suivi par exactement deux expressions bien formées. Cela peut être analysé facilement en utilisant la récursivité

Si vous parssez un arbre et obtenez une variable, renvoyez la variable. Si vous analysez un arbre et obtenez un opérateur, analysez les deux arbres suivants comme des sous-arbres droite/gauche.