Arborescence d'expression binaire C++: comment imprimer une expression infixe avec des parenthèses appropriées?

Question

Maintenant, j'ai cet algorithme d'impression simple qui imprime des parenthèses parfaites. Le problème est, les parenthèses ne sont pas toujours nécessaires, et j'ai besoin de comprendre comment ne pas les imprimer quand ils ne sont pas nécessaires.

Ma fonction actuelle:

void printIn(Node* t){ 

if(t!= NULL) { 
    if(isleafNode(t)) 
     cout << t->element; 
    else {  
     cout << "("; 
     printIn(t->left); 
     cout << t->data; 
     printIn(t->right); 
     cout << ")"; 
     } 
    } 

Le problème ici est que certaines expressions Postfix, telles que 2 50 + 8 + peuvent être imprimées en infix que 2 + 50 + 8 instad de ((2 + 50) + 8))

Voici un tableau de suffixes à infixer à quoi cela devrait ressembler. Le mien ajoute juste des parenthèses autour de l'extérieur, et à toute l'addition n'importe quoi.

4 50 6 + +   4 + (50 + 6) 
4 50 + 6 +   4 + 50 + 6 
4 50 + 6 2 * +  4 + 50 + 6 * 2 
4 50 6 + + 2 *  (4 + (50 + 6)) * 2 
a b + c d e + * * (a + b) * (c * (d + e)) 

Voici un tableau de la façon dont le mien regard:

4 50 6 + +   (4 + (50 + 6)) 
4 50 + 6 +   ((4 + 50) + 6) 
4 50 + 6 2 * +  ((4 + 50) + (6 * 2)) 
4 50 6 + + 2 *  ((4 + (50 + 6)) * 2) 
a b + c d e + * * ((a + b) * (c * (d + e))) 

Comment puis-je réparer mon algorithme pour éliminer entre parenthèses supplémentaires? p faut garder à l'esprit que j'ai une fonction getPrecedence (string) qui renvoie 1 pour priorité élevée (* ou /) et 0 pour priorité faible (+ ou -)

Answer 1

Lors de l'impression d'un arbre d'expression sous la forme de infix vous ne besoin d'imprimer des parenthèses autour des sous-expressions (c'est-à-dire les enfants) où l'opérateur a une priorité inférieure à celle de l'opérateur de l'expression principale (c'est-à-dire parent). Par exemple, prenez l'arbre d'expression suivant (en notation postfixée) et sa forme d'infixe.

4 5 6 + 7 * +  4 + (5 + 6) * 7 

Notez qu'une parenthèse est nécessaire autour de 5 + 6 puisque l'opérateur de la sous-expression 5 6 + a priorité inférieure à l'opérateur de la principale expression 5 6 + 7 * mais il n'est pas nécessaire pour la sous-expression 5 6 + 7 * puisque l'opérateur a une plus grande priorité que l'opérateur de l'expression principale 4 5 6 + 7 * +

En utilisant cette information, il est facile de modifier l'algorithme dans la question pour éviter les parenthèses quand ils ne sont pas nécessaires. Notez que puisqu'il n'y a pas de pointeurs parents dans l'arbre, il est plus facile de faire vérifier par le parent si l'un des enfants a besoin de parenthèses que de faire en sorte que le nœud mette des parenthèses autour de lui.