Discussion :

[sihamnet]

Bonjour,

une petite explication de l'algo avant tout avec l'exemple suivant :

Le calcul ((1 + 2) × 4) + 3 peut se lire intuitivement :
je mets 1, (1)
j'ajoute 2, ( 2 + )
je multiplie par 4, (4 ×)
j'ajoute 3. (3 +)
ce qui donne simplement l’opération développée suivante 1 2 + 4 × 3 +


Bon, j'ai trouvé un code (si dessous) qui fait le calcul mais il ne permet pas d'afficher l’opération développée avant de faire le calcul et je veux savoir s'il ya une possibilité de faire sans passer par les piles

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* evaluation d'une formule arithmetique (+, -, * et entiers) et sans vraies parentheses */
 
#include <stdio.h>
 
/* à cause de strtol() */
#include <stdlib.h>
 
#define Base 10
 
/* a est la chaine à évaluer, les nombres sont écrits en base 10 */
int calcul (char *a)
{
  char *p = a;
  char *r = a;
  char **q = &r;
/*
La chaine est vue comme une grande somme/différence de termes qui sont des produits.
Chaque produit est placé dans P et une fois complètement calculé, il est ajouté à S.
La chaine  est supposée bien construite ie elle représente une formule mathématique valide.
*/
  int P = 1, S = 0;
  char signe = '+';
 /* tant qu'on a pas examiné toute la chaine */
  while (**q != '\0')
    {
      do /* Evaluation du produit courant */
        {
          if (*p == '(')
            {
              p++;
              P *= strtol (p, q, Base);
              *q = *q + 1;
              p = *q + 1;
            }
          else
            P *= strtol (p, q, Base);
          p = *q + 1;
        }
      while (**q == '*');
/* On ajoute ou on retranche le produit au S courant */
      if (signe == '+')
        S += P;
      else
        S -= P;
/* on réinitialise */
      signe = **q;
      P = 1;
    }
  return S;
}
 
int main (void)
{/* Exemple illustratif */
  char *a =
    "2*3+8*2*4-8*4*2+8*(-9)*(-7)-8*(-10)*5-9*(-7)*(-9)*11+(-2)*3+5555";
 
  printf ("%s =\n%d\n", a, calcul (a));
  return 0;
}

[kwariz]

Bonjour,

je ne comprends pas vraiment ta question. Que veux-tu faire ? Passer d'une expression infixe comme "-1+2*(3+4)" à son expression suffixe (rpn) "-1 2 3 4 + * +" puis donner le résultat de l'opération ?

[sihamnet]

Bonjour,

je ne comprends pas vraiment ta question. Que veux-tu faire ? Passer d'une expression infixe comme "-1+2*(3+4)" à son expression suffixe (rpn) "-1 2 3 4 + * +" puis donner le résultat de l'opération ?

en effect je veux passer d'une opération arithmétique simple du genre
((1 + 2) × 4) + 3
à la notation polonaise inverse expliquée comme suit
je mets 1, (1)
j'ajoute 2, ( 2 + )
je multiplie par 4, (4 ×)
j'ajoute 3. (3 +)

ce qui donne simplement 1 2 + 4 × 3 +

et à la fin après affichage de la NPI faire le calcule
merci

[kwariz]

Pour transformer une expression infixe en npi simplement alors tu peux utiliser un algorithme à base de deux piles (il est classique et tu trouveras de nombreuses références grâce à google). Ton code est issu d'un tel algorithme mais calcule le résultat en place. Si tu veux afficher et manipuler l'expression en npi alors il te faudra garder la pile finale qui va contenir l'expression.
Une autre approche serait d'utiliser des arbres binaires pour représenter l'expression. Un parcours infixe te donne l'expression classique, un parcours suffixe te donne la npi.

Je suppose qu'il s'agit d'un exercice qui te demande d'utiliser des piles ?

Edit: ok ... tu ne veux pas utiliser les piles
Pourtant l'algorithme utilisant les piles est le plus simple, celui avec les arbres est un peu plus complexe ...

[ternel]

Sans pile explicite, tu auras une fonction récursive, dont la pile d'appel sera la pile implicite.

[Médinoc]

Edit: ok ... tu ne veux pas utiliser les piles
Pourtant l'algorithme utilisant les piles est le plus simple, celui avec les arbres est un peu plus complexe ...

Et parcourir un arbre sans pile est encore plus complexe! (et n'est possible que si l'arbre est doublement chaîné).

[Bktero]

J'ai du mal avec cette notation.... Je lis qu'elle est utile car elle supprime le besoin de parenthèses. Or, sur l'exemple donné, il suffit de ne pas tenir compte de la priorité des opérateurs et d'effectuer les calculs de gauche à droite pour avoir le résultat :
((1 + 2) × 4) + 3 --> 1 + 2 × 4 + 3 --> 3 x 4 + 3 --> 12 + 3 --> 15
Si quelqu'un a un exemple plus parlant je suis preneur...

[kwariz]

Et parcourir un arbre sans pile est encore plus complexe! (et n'est possible que si l'arbre est doublement chaîné).

Bah avec une structure récursive on a intérêt à utiliser des algorithmes récursifs qui sont souvent plus simples à exprimer et [troll]bien plus élégants [/troll]. Évidemment on utilise implicitement le stack comme pile ...
Le gros avantage de la représentation par arbre est d'obtenir aisément les 3 notations avec un simple parcours.

J'ai du mal avec cette notation.... Je lis qu'elle est utile car elle supprime le besoin de parenthèses. Or, sur l'exemple donné, il suffit de ne pas tenir compte de la priorité des opérateurs et d'effectuer les calculs de gauche à droite pour avoir le résultat :
((1 + 2) × 4) + 3 --> 1 + 2 × 4 + 3 --> 3 x 4 + 3 --> 12 + 3 --> 15
Si quelqu'un a un exemple plus parlant je suis preneur...

La notation infixe nécessite un parenthésage pour passer outre les priorités des opérateurs.
Sans priorités et sans parenthèse il y a ambigüité sur 1+2*3 qui peut donner (1+2)*3 ou 1+(2*3).
La notation postfixe en revanche n'en a pas besoin, 1 2 + 3 * n'a qu'une interprétation possible (1+2)*3, tout comme 1 2 3 * + -> 1+(2*3) mais elle n'est pas unique -> 2 3 * 1 +