un exercice à résoudre

Version imprimable

20/04/2008, 22h34
km_mino

un exercice à résoudre

on dit qu'une expression arithmétique est complètement parenthésée si chaque terme situé de part et d'autre d'un opérateur est entouré d'une parenthèse
expl : (a*(b+(c/d)))
pour eviter cette nécéssité un mathématicien a proposé une notation dite polonaise
dans laquelle les opérateurs suivent immédiatement les opérandes sur lesquelles ils agissent
exple
(a*(b+(c/d))) nous donne le résultat suivant abcd / + *
donc
ce qui se passe c'est dans une pile1 on met les opérateurs
dans une pile 2 on met les opérandes
et lorsque on rencontre une parenthèse ouvrante on ne fait rien
et lorsque c'est une parenthèse fermante on dépile p2 et empile p1
en fin de l'expression on obtient la pile 2 vide alors on dépile p1 dans p2
je voudrais bien que vous m'aidez à résoudre cette programme avec c++ parce que la résolution que j'ai trouvé n'a pas fonctionné
j'attends vos réponses le plutot possible
21/04/2008, 00h09
Leole

J'ai du mal à comprendre le code avec lequel tu as un problème. :)
21/04/2008, 10h17
Emmanuel Deloget

Citation:

Envoyé par km_mino

j'attends vos réponses le plutot possible

Je suis content de la confiance que tu nous porte, et suis particulièrement heureux de répondre à tes ordres, en t'aidant immédiatement à faire tes devoirs.

Ah non, mince.
21/04/2008, 18h03
km_mino

primo je ne vous ordonne pas de m'aider mais je vous demande de me porter de l'aide
secondo ce sont pas mes devoirs mais c'est un problème que j'ai rencontré et que j'ai pas pu résoudre alors j'ai demandé de l'aide
en + personne n'est parfait on apprend les choses par le recours à ceux qui connaissent
merci de toute façon
21/04/2008, 18h32
zais_ethael

Si au moins tu nous expliquais en quoi consiste ton programme.
La notation polonaise je connais, bien que la structure de données que tu as choisis pour représenter une formule me semble assez étrange (des piles??) je ne peux te donner aucun conseil vu que je ne comprends pas quelles sont les données de départ et celles d'arrivée.
C'est quoi le but ? Convertir une expression complètement parenthésée en expression polonaise ? Le contraire ? Résoudre une expression sous l'une ou l'autre forme ?
22/04/2008, 23h01
km_mino

Convertir une expression complètement parenthésée en expression polonaise c'est ça le but du programme mais en utilisant les piles de la manière avec laquelle j'ai expliqué au sujet.
j'y arrive presque mais pas totalement
23/04/2008, 09h47
befalimpertinent

Tu trouveras personne ici pour te donner ton code tout fait donc montre nous ce que tu as déjà fait et là où tu bloques.

L'algorithme est simple :

1) création de la pile

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
39
40
41
42
43
44
liste 1 va contenir l'opération finale à exécuter
liste 2 est une liste temporaire, utilisée pour construire l'expression
liste R est la liste qui permettra de calculer le résultat
 
pour chaque symbole de l'expression
 
  si le symbole est une opérande
    insertion de l'opérande à la fin de liste 1
  fin si
 
  si le symbole est un opérateur 
    stocker l'opérateur dans op1
    si liste 2 est non vide
      faire 
        op2 = pop liste 2
        si la précédence de op1 est supérieur à la précédence de op2      
          insertion de op2 à la fin de liste 1
        fin si
      tant que la précédence de op1 est supérieure à la précédence de op2
    sinon
      push de op2 sur liste 2 (on le remet en place)
    fin si
    push de op1 sur liste 2
  fin si
 
  si le symbole est une parenthèse ouvrante
    push d'un marqueur P sur liste 2
  fin si
 
  si le symbole est une parenthèse fermante
    faire 
      op = pop liste 2
      si op n'est pas le marqueur P 
        insertion de op à la fin de liste 1
      fin si
    tant que op n'est pas le marqueur P
  fin si
 
fin pour
 
pour chaque opérateur de liste 2
  op = pop liste 2
  insertion de op à la fin de liste 1
fin pour

Un exemple avec une expression complexe: 45*(5*8+2)/7+78*4

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
Iteration Symbole Liste 1                                 Liste 2
--------- ------- --------------------------------------- ------------------------------------
   1      45      45
   2      *       45                                      *
   3      (       45                                      P *
   4      5       45 5
   5      *       45 5                                    * P *
   6      8       45 8 5                                  * P *
   7      +       45 8 5 *                                + P *
   8      3       45 8 5 * 2                              + P *
   9      )       45 8 5 * 2 +                            *
  10      /       45 8 5 * 2 +                            / *
  11      7       45 8 5 * 2 + 7                          / *
  12      +       45 8 5 * 2 + 7 / *                      +
  13      78      45 8 5 * 2 + 7 / * 78                   +
  14      *       45 8 5 * 2 + 7 / * 78                   * +
  15      4       45 8 5 * 2 + 7 / * 78 4                 * +
  fin     n/a     45 8 5 * 2 + 7 / * 78 4 * +

Rappel sur la précédence des opérateurs Prec(op):

Prec(*) = Prec(/) > Prec(+) = Prec(-)

2) Evaluation
liste 1 contient maintenant l'expression entière, et liste R est censée contenir le résultat:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
tant que liste 1 n'est pas vide
  s = pop liste 1
 
  si s est une opérande
    push s dans liste R
  fin si
 
  si s est un opérateur
    si liste R contient moins de 2 symboles ==> erreur
    operande1 = pop liste R
    operande2 = pop liste R
    resultat = operande2 OPERATEUR operande1
    push resultat dans liste R
  fin si
 
fin tant que

A la fin, il ne doit y en rester qu'un (dans liste R, s'entend. Inutile de couper la tête à tout le monde), et c'est bien évidemment le résultat attendu.

Dans notre exemple, on effectue l'opération comme suit:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Iteration Liste 1                                 Liste R
--------- --------------------------------------- ------------------------------------
  1       8 5 * 2 + 7 / * 78 4 * +                45
  2       5 * 2 + 7 / * 78 4 * +                  8 45
  3       * 2 + 7 / * 78 4 * +                    5 8 45
  4       2 + 7 / * 78 4 * +                      40 45
  5       + 7 / * 78 4 * +                        2 40 45
  6       7 / * 78 4 * +                          42 45
  7       / * 78 4 * +                            7 42 45
  8       * 78 4 * +                              6 45
  9       78 4 * +                                270
 10       4 * +                                   78 270
 11       * +                                     4 78 270
 12       +                                       312 270
 13       (vide)                                  582

Voilà!

23/04/2008, 14h58
Médinoc

Ah, cela confirme donc qu'une seule pile est nécessaire (en plus des flux d'entrée et de sortie) pour convertir une expression infixe en expression postfixe...

Par contre, j'ai du mal à comprendre pourquoi le 8 a été inséré entre le 45 et le 5... :?

Edit: OK, ça me rassure.
23/04/2008, 15h15
Emmanuel Deloget

Citation:

Envoyé par Médinoc

Ah, cela confirme donc qu'une seule pile est nécessaire (en plus des flux d'entrée et de sortie) pour convertir une expression infixe en expression postfixe...

Par contre, j'ai du mal à comprendre pourquoi le 8 a été inséré entre le 45 et le 5... :?

C'est une erreur - (for heureusement, elle ne change rien...)