Parse pile dans un arbre binaire?

Question

Je fais un programme chargé de convertir une expression mathématique telle que (2+4)*(4/3) en un arbre binaire, puis de le manipuler. Tout d'abord, lors de l'analyse, j'ai transformé la chaîne en deux piles, opérandes et opérateurs. Comment puis-je déterminer ce que la racine doit être, étant donné que dans mon exemple ci-dessus l'arbre devrait ressembler à ceci:

 * 
    /\ 
    + /
    /\ /\ 
    2 4 4 3 

Notez que la racine est * qui est l'opérande la plus externe. Mais sur mon pile d'opérandes, il ressemble à ceci:

/ 
* 
+ 

Et il pourrait y avoir des cas comme (2+4+3)*4 ou 2*((4+1)/3).

Comment puis-je déterminer quel opérande doit être la racine de mon arbre binaire?

Answer 1

Convertissez votre expression infixe en notation de préfixe ou de suffixe. Vous ne pouvez pas vraiment avoir une pile d'opérateur appropriée sans cela.

Dans la notation postfix, l'expression (2+4)*(4/3) ressemblerait à ceci:

2 4 + 4 3/* 

Donc, vous avez la multiplication apparaissant à la fin qui pourrait être inséré dans l'arbre comme sa racine. L'évaluation d'une expression postfix est beaucoup plus facile pour un ordinateur car le regroupement n'est pas nécessaire.

Answer 2

Vous ne pouvez pas simplement placer les opérateurs sur votre pile dans l'ordre dans lequel ils apparaissent dans votre expression. Une fois que vous avez fait cela, vous perdez la capacité de désambiguïser, comme vous l'avez identifié.

Voir par exemple. http://en.wikipedia.org/wiki/Shunting_yard_algorithm pour un algorithme pour analyser la notation infixe.

Answer 3

Vous pouvez utiliser une pile pour implémenter un infixe dans l'arborescence d'expression binaire. Ce lien a une implémentation C de:

An infix to binary-expression-tree parser that usings two stacks

un pour les opérateurs et un autre pour opérandes, qui dérivent tous d'une classe de noeud de base.