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

binary-tree c++ expression-trees tree

Question

En ce moment, j'ai cet algorithme d'impression simple qui imprime des parenthèses parfaites. Le problème est que les parenthèses ne sont pas toujours nécessaires et que je dois trouver un moyen de ne pas les imprimer lorsqu'elles 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 postfixes, telles que 2 50 + 8 + peuvent être imprimées en infixe sous la forme 2 + 50 + 8 instad de ((2 + 50) + 8))

Voici un tableau de postfix à infixer à quoi il devrait ressembler. La mienne ne fait qu'ajouter des parenthèses autour de l'extérieur et à toute addition quoi qu'il en soit.

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 mon apparence:

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 corriger mon algorithme pour éliminer les parenthèses supplémentaires? p N'oubliez pas que j'ai une fonction getPrecedence (chaîne) qui renvoie 1 pour une priorité élevée (* ou /) et 0 pour une priorité faible (+ ou -).

Réponse populaire

Lors de l'impression d'une arborescence d'expression sous forme infixe, il suffit d'imprimer des parenthèses autour des sous-expressions (enfants) lorsque l'opérateur a une priorité inférieure à celle de l'opérateur de l'expression principale (parent).

À titre d'exemple, prenons l'arbre d'expression suivant (en notation postfixe) et sa forme infixe.

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

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

En utilisant ces informations, il est facile de modifier l’algorithme dans la question pour éviter les parenthèses quand elles ne sont pas nécessaires. Notez qu'il n'y a pas de pointeur parent dans l'arborescence, il est donc plus facile de faire en sorte que le parent vérifie si l'un des enfants a besoin d'une parenthèse plutôt que de faire en sorte que le nœud mette une parenthèse autour de lui.




Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi