Salut,

j'ai un petit programme en C à faire et je bloque sur une des fonctions.

Au départ j'ai une expression mathématique simple (des nombres et seulement les opérateurs + - * /) que je lis et que je mets dans un arbre binaire. Là pas de problème, j'ai une structure de "noeud"

struct Noeud{
char op;
char * valeur;
Noeud * gauche,* droite;
}

Je dois à partir de l'arbre afficher l'expression en format préfixe et infixe. Pour ça j'ai des fonctions récursives qui parcourent l'arbre et affichent les éléments dans le bon ordre.

Le problème, c'est que je dois afficher des parenthèses.

En préfixe, il me faut des parenthèses avant l'opérateur et après sa 2e opérande (du genre (+ 2 3) ou encore (+ (- 2 1) (+ 3 2)), etc).

En infixe je dois afficher l'expression avec le minimum de parenthèses (en tenant compte de la priorité des opérateurs donc).

J'ai beau chercher, je n'arrive pas à trouver l'algo qui me permettrait de mettre les parenthèses au bon endroit.

En préfixe je vois bien que ça doit marcher par "bloc" (opérateur et ses opérandes) mais j'arrive pas à l'écrire en C

Quelqu'un aurait une idée de comment faire ? J'ai essayé plein de trucs et ça n'a rien donné.

Merci.

Comment sais-tu que ton noeud est un noeud terminal(une feuille)?
Le pseudo algo pour la préfixe c'est:
AfficherPrefixe(noeud)
if (isTerminal(noeud))
print noeud.valeur
else
print '('
print noeud.op
AfficherPrefixe(noeud.gauche)
AfficherPrefixe(noeud.droite)
print ')'
end

A toi de transformer ça en C. Si tu as compris le principe, l'affichage en infixe ne te posera pas de problème.

Merci, j'avais finalement trouvé pour le préfixe 10 min après avoir posté

Par contre pour l'infixe je dois respecter la priorité des opérateurs, donc (2+4)*3 a besoin de parenthèses mais 2*4+3 n'en a pas besoin.

Selon moi il faut connaître les opérateurs à l'avance et les comparer pour savoir si on met des parenthèses ou non.

Pour gérer ça tu peut ajouter un paramètre à la fonction récursive qui sera la niveau de priorité de l'operateur precedent.
Si l'opérateur courant à une priorité plus forte il n'y a pas besoin des parenthèses. L'appel initial donne la priorité la plus faible(0 par exemple) comme ça il n'y a pas de parenthèses qui englobent tout. Ca donnerait ça en pseudo-code:
http://pastebin.com/zw9SZwEC

En vrai c'est un peu plus compliqué que ça car là ça ne gère pas 1 + 1 + 1, ça va faire 1 + ( 1 + 1) normalement. Il faut gérer le fait qu'un opérateur soit associatif à droite ou à gauche et traiter différemment l'appel sur le noeud droit ou gauche.

Merci.

Par contre ça marche seulement selon des cas assez précis, le reste du temps j'ai des parenthèses en trop.
Par exemple j'ai (2*3+(4+5)) alors que je veux 2*3+4+5 ou alors quand j'ai seulement des opérateurs de même niveau.

Il y a moyen d'arranger ça en gardant cette notion de priorité ou alors il faut utiliser totalement une autre méthode ?

J'ai un peu modifié et finalement je retombe sur ce que tu dis : avec les opérateurs + et - ça met trop de parenthèses, genre 1 + 1 + 1 ça me fait (1+(1+1)).

Si t'a bien fait ce que j'ai dit tu devrai avoir 1 + (1 + 1) plutôt. Pour gérer les parenthèses qui restent, comme dit plus haut il faut que tu traite différemment les fils gauches et droits. Moi je rajouterai un paramètre à la fonction qui dit si le noeud est un noeud gauche ou droit. Alors on affiche les parenthèses dans ce cas:
-l'opérateur courant a une priorité plus faible que le précédent
-ou alors les deux opérateurs ont la même priorité mais sont différents, associatifs à gauche et on est sur un noeud droit (ou associatifs à droite et on est sur un noeud gauche).

+, -, / et * sont tous associatifs à gauches et puissance est associatif à droite si tu doit le gérer.