Version imprimable
Bonjour,
Est ce qu'il y a quelqu'un qui a une idée pour déveloper une équation arithmétique en éliminant les parenthéses.
par example: on a cette équation:
qui doit devenir:Citation:
a=(b-x)*(2+t)+m
J'ai essayé avec la notation polonaise inverse mais non, c'était pas une bonne idée.Citation:
a = b*2 + b*t - x*2 - x*t +m
?
Merci d'avance
Au contraire, la notation polonaise inversée est une très bonne idée.
Grâce à cette notation, tu vas obtenir un arbre binaire : si un nœud est un opérateur, alors il a un fils gauche et un fils droit. Sinon (si c'est un nombre ou une lettre) c'est une feuille.
Il te faut simplement distribuer les opérandes pour les multiplications et divisions.
Si un nœud * ou / possède un opérateur + ou - en fils droit, alors il faut distribuer le sous-arbre gauche sur les deux fils du fils droit.
L'opérateur du fils droit devient le père. Il gagne 2 fils avec l'opérateur distribué.
Tu raisonnes de la même façon avec un opérateur + ou - sur le fils gauche (attention, le / n'est pas commutatif).
Tu reconstruit ton arbre jusqu'à ce qu'il ne possède plus un nœud * ou / avec un fils + ou -.
C'est compliqué à expliquer, mais fait un dessin, ça deviendra limpide.
Oui avec la notation polonaise inversée, il va me donner:
et pas la forme dévelopée que je voulais avoir telque..Citation:
b x - 2 t + * m +
Citation:
b*2 + b*t - x*2 - x*t +m
Je t'ai expliqué qu'il "suffit" de retravailler l'arbre obtenue de manière très simple pour distribuer les opérateurs * et / sur + et -.
La notation polonaise toute seule ne sert à rien.
Histoire de donner un aperçu a ce qui est dit ,voila a quoi ressemble un arbre
Pièce jointe 97672
donc comme tu remarque un noeud est une opération , une feuille est le reste
une lecture de gauche a droite de cet exemple donne 56+18*3
fait attention a l'ordre de priorité des opération
Non ! Attention aux parenthèses !Citation:
Envoyé par cobra150
La formule est : ( 56 + 18 ) * 3
Merci pour l'arbre, je n'avais pas le courage de faire une image. Mais c'est tellement plus parlant :ccool:
Je reprends mon explication en me basant sur l'illustration.
Tu cherches à distribuer la multiplication. Ton programme va détecter que le nœud "*" à un fils "+". Donc le nœud "*" va être supprimé pour reconstruire un nouveau sous-arbre. Il faut donc créer un nouveau nœud "+" (à la place du nœud "*") avec un fils gauche "*".
Ce fils gauche "*" aura un fils gauche "56" et un fils droit "3".
Tu ajoutes ensuite un fils droit "*" au nœud "+".
Ce fils droit aura un fils gauche "18" et un fils droit "3".
Voila, le sous-arbre tel qu'imagé au dessus est développé.
Il suffit de généralisé à un arbre quelconque.
Ici, "56" et "18" étaient des nombres. L'algorithme est généralisable à un sous-arbre quelconque avec une simple fonction récursive.
