[debutant]arithmétique

Ou trouver un algo qui permet de convertir une expression infixe en expression suffixe
Ex
1 + 2 * 3 :arrow: infixe
1 2 3 * + :arrow: suffixe Notation polonaise inversée

J'aimerais trouver un algo qui marche avec ou sans parenthèse.

Je ne sais pas si c'est la meilleure solution mais tu peux construire un arbre binaire à partir de ton expression prefixe (R, G, D) et faire un parcours en ordre postfixe (G, D, R).
Je pense que cette solution est convenable car tu fais deux parcours de taille n si n est la taille de ton expression. Je ne vois pas comment on peut faire un algorithme meilleur que linéaire cependant on peut peut-être faire la transformation en une seule passe mais je ne vois pas.

bien le bonjour,

la solution proposée par nicolas581 est très élégante. Attention cependant aux priorités opératoires. dans le cas du 1+2*3, il n'y a pas de soucis, l'opérateur principal de l'expression est bien le premier trouvé mais si nous avions eu 1*2+3, il aurait quand même fallu couper à +. Si on parenthèse bien tout, ce problème disparait, il suffit alors de compter les parenthèses ouvertes.

Pour règler ce problème de paranthésage le plus simple dans un premier temps serait de créer une fonction qui fait d'une expression une expression correctement parenthésée puis de voir par la suite si l'on peut créer un arbre sans passer par cette étape.

ouaip, mais le problème reste entier comment construire un arbre correct avec une expression infixe, j'avais démarré avec cette idée mais je n'ai pas trouvé de solution.
Moi je pensais plutôt à resoudre le problème avec deux piles différentes, une pour les opérantes et une pour les opérateurs.

en supposant que tu possèdes une expression entièrement parenthésée (même autour des multiplications) , la construction de l'arbre se ferait de la manière suivante :

repérage de l'opérateur principal, en tenant compte des parenthèses. Donc, tout d'abord il faut regarder si toute l'expression est parenthésée. Si c'est le cas, ses parenthèses extérieures sont à supprimer. Ensuite, on parcourt l'expression en comptant les parenthèses ouvertes. Lorsqu'on n'a plus aucune parenthèse d'ouverte, cela signifie qu'on est en présence de l'opérateur principal. On sait donc où séparer notre arbre.
Le noeud de l'arbre contient le dit opérateur principal, le fils gauche contiendra une version récursivée de cette même analyse sur l'expression précédent l'opérateur principal et le fils droit contiendra la même chose pour l'autre morceau de l'expression.

La récursivité s'arrête quand on est en présence d'un symbole ou d'un nombre ne pouvant pas être réduit.

Citation:

---

Envoyé par c-top

ouaip, mais le problème reste entier comment construire un arbre correct avec une expression infixe, j'avais démarré avec cette idée mais je n'ai pas trouvé de solution.
Moi je pensais plutôt à resoudre le problème avec deux piles différentes, une pour les opérantes et une pour les opérateurs.

---

C'est la bonne idée sauf qu'il ne faut qu'une pile.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

// Pseudo-code   string depart = "1 + 2 * 3"; string arrivee; stack p; char c;   Pour i = 0 à longueur(depart) Faire Si est_un_operateur(depart[i]) Alors Empiler(p, depart[i]); arrivee = arrivee + " " Sinon Si depart[i] != " " Alors arrivee = arrivee + depart[i]; Fin Si Fin Si Fin Pour Pour i = 0 à taille(p) Faire c = Depiler(p); // Selon comment Depiler est codée elle peut renvoyer une pile ou un élément arrivee = arrivee + " " + c; Fin Pour

---

Yabo > es-tu sûr de ton algorithme car sur l'exemple suivant :
((a+b)+(c*d)) en expression infixe je me retrouve avec l'expression postfixe suivante :
a b c d + + * alors que le résultat devrait être a b + c d * +
On a avec cette expression l'arbre suivant :
+
+ *
a b c d

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/* Construction d'un arbre à partir d'une expression correctement parenthésée  tg : expression sur la gauche de l'arbre.  td : expression sur la droite de l'arbre. */   arbre expression (String e) // cas d'arrêt un seul élément : constante ou littéral si (e[0] != '(' ) retourner cons_arbre(e[0], vide, vide) ; nbpar = i = j = 0 ; i ++; // on remplit la gauche de l'expression faire si (e[i] = '(' ) nbpar++; sinon si (e[i] = ')' ) nbpar -- ; tg[j] = e[i]; i++; j++; tant que (nbpar > 0); // la racine racine = e[i] ; i++; // on remplit à droite nbpar = j = 0; faire si (e[i] = '(' ) nppar++; sinon si (e[i] = ')' ) nbpar -- ; td[j] = e[i]; i++; j++; tant que (nbpar > 0); retourner cons_arbre(racine, expression(tg), expression(td) ;

---

Après tu n'as plus qu'à faire le parcours en post-ordre et c'est gagné.
Problème que je vois dans cette méthode les expressions doivent être correctement parenthésées et bien formée si tu as a+b problème, i.e
(1+(2*3)) ((2*x)/x) ou même (a+x) mais l'algo que j'ai donné doit pouvoir supporter quelques améliorations que je te laisse trouver :wink:

Après de multiples recherches ma conclusion est il n'y a pas de réponse triviale. On m'a conseillé d'utiliser un analyseur syntaxique du type de antlr
Bon tout ça m'a l'air plutôt complexe :roll:
Je vous tiens au courant.

Citation:

---

Envoyé par nicolas581

Yabo > es-tu sûr de ton algorithme car sur l'exemple suivant :
((a+b)+(c*d)) en expression infixe je me retrouve avec l'expression postfixe suivante :
a b c d + + * alors que le résultat devrait être a b + c d * +

---

Non tu n'obtiens pas ca.

Tu obtiens :
((a b) (c d)) * + +

J'ai pas fais la gestion des parenthèses dans l'algo mais c'est simple :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

// Pseudo-code   string depart = "1 + 2 * 3"; string arrivee; stack p; char c;   Pour i = 0 à longueur(depart) Faire Si est_un_operateur(depart[i]) Alors Empiler(p, depart[i]); arrivee = arrivee + " " Sinon Si depart[i] = ")" Alors c = Depiler(p); arrivee = arrivee + ") " + c + " "; Sinon Si depart[i] != " " Alors arrivee = arrivee + depart[i]; Fin Si Fin Si Fin Si Fin Pour Pour i = 0 à taille(p) Faire c = Depiler(p); // Selon comment Depiler est codée elle peut renvoyer une pile ou un élément arrivee = arrivee + " " + c; Fin Pour

---

Avec ca l'expression "((a + b) + (c *d))" donne "((a b) + (c d) *) +"

Citation:

---

Envoyé par c-top

Après de multiples recherches ma conclusion est il n'y a pas de réponse triviale. On m'a conseillé d'utiliser un analyseur syntaxique du type de antlr
Bon tout ça m'a l'air plutôt complexe Rolling Eyes
Je vous tiens au courant.

---

Ni la méthode avec l'arbre, ni la mienne ne sont des méthodes qui nécessite un algo "complexe" ;)

Merci a tous pour votre participation,
çà y est j'ai écrit les classes permettant d'obtenir un arbre à partir d'une expression arithmétique comportant [ (, ), *, /, + * nombres et variables ]. Plus les différents parcours/ postfixe, prefixe, ...
Bon il ne reste plus que l'analyse classique... :wink: