Discussion :

[c-top]

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

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

[nicolas581]

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.

[khayyam90]

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.

[nicolas581]

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.

[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.

[khayyam90]

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.

[Yabo]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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 * +
On a avec cette expression l'arbre suivant :
+
+ *
a b c d

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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
Je vous tiens au courant.

[Yabo]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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) *) +"

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"

[c-top]

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...