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

[Médinoc]

(1 + 2) * (4 + 3) ---> 1 2 + 4 3 + *

Bien sûr, l'algo par excellence pour exécuter ça, c'est une pile.

• push 1 --> 1
• push 2 --> 1 2
• Op + ----> 3
• push 4 --> 3 4
• push 3 --> 3 4 3
• Op + ----> 3 7
• Op * ----> 21

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

[ternel]

ah non, 2 3 * 1 + n'est pas 1 2 3 * +.
La première est (2*3)+1 et la seconde 1+(2*3)

La valeur est la même, parce que + et * sont symétriques.
Ca devient flagrant avec / ou -.

[kwariz]

Je parlais de la nécessité de définir des priorités entre les opérateurs et de la nécessité d'utiliser les parenthèses pour lever les ambigüités. Si on prend l'expression suivante :

Une expression infixe représentant cet arbre sera obligée d'utiliser un parenthésage même si on a défini une priorité sur les opérateurs ; d'ailleurs quelles que soient les priorités définies on pourra toujours construire une expression nécessitant un parenthésage.
Au contraire, les expressions infixes n'ont jamais besoin ni de parenthésage ni priorité sur les opérateurs (enfin tant qu'un opérateur n'a qu'une seule arité).

Mais tu as raison 2 3 * 1 + et 1 2 3 * + ne sont pas issues du parcours postfixe du même arbre. Les deux arbres associés ne sont pas égaux mais chacun pourrait être issu du parsing de la même expression 1+2*3.

[Médinoc]

N'y a-t-il pas un qualificatif du genre "isomorphe" ou "équivalent" pour de tels arbres, dont les seules différences concernent des opérations commutatives?

[ternel]

Je dirai plutôt "mathématiquement égales", mais j'imagine qu'"équivalentes" irait.

[kwariz]

Concernant les arbres qui donnent 2 3 * 1 + et 1 2 3 * + ils sont isomorphes. Mais les arbres pour 1 2 - et 2 1 - aussi pourtant là les expressions ne sont pas égales, effectivement à cause de la non commutativité de -. Un autre cas est l'expression 1 + 1 + 1 + 1 pour laquelle on peut dériver un arbre peigne et un arbre complet qui ne sont pas isomorphes :

[sihamnet]

je vous remercie pour vos suggestions,
et j'aimerais bien que vous m'aidiez à corriger le code que j'ai implémenté jusqu'à maintenant

je suis encore débutante et tout vos conseils seront utiles pour moi

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
typedef struct
{
     int * t;
     int taille;
     int sommet;
}pile;
 
////////////////////////////////////////
int pleine(pile p)
{
    if(p.sommet==p.taille)  return 1;
    else                return 0;
}
////////////////////////////////////////
void empiler(pile *p, char x)
{
     if(pleine(*p)==1)   
     printf("pile pleine !\n");
     else{
          (*p).t[(*p).sommet] = x;
          (*p).sommet++;
     }     
}
////////////////////////////////////////
int vide(pile p)
{
    return (p.sommet==0);
}
////////////////////////////////////////
int depiler(pile *p)
{
     (*p).sommet--;
     return (*p).t[(*p).sommet];
}
////////////////////////////////////////
void RAZ(pile *p)
{
     (*p).sommet = 0;
}
////////////////////////////////////////
 
 
 
int main()
{
  pile npi1;
  pile npi2;
  char *oper;
  int n,i,res=0,v1,v2,u;
 
  do{
        printf("Entrez la taille de la chaine : \n");
        scanf("%d",&n);
  }while(n<0);
 
  oper = (char*)malloc(n*sizeof(char));
 
  i=0;
  while(oper[i] != '\0') {i++;}
  u=i;
  npi1.taille = (int*)malloc(u*sizeof(char));
 
  printf("donnez un operation a resoudre sans parentheses svp ! \n");
  scanf("%s",oper);
 
  printf("voilà l'operation classique que vous avez entrez :p \n");
  puts(oper);
 
 
  while(oper[i]!='\0')
  {
        npi1.sommet = NULL;
        if(oper[i] != '*' && oper[i] != '+')
        empiler(npi1,&oper[]);
        else if(oper[i] == '+')
        { 
             v1 = depiler(&npi1);
             v2 = depiler(&npi1);
             res = v1+v2;
             empiler(&npi1,res);
        }
        else if(oper[i] == '*')
        { 
             v1 = depiler(&npi1);
             v2 = depiler(&npi1);
             res = v1+v2;
             empiler(&npi1,res);
        }
 
  res = depiler(&npi1);
  printf(res);
 
  getch();	
  return 0;
}

[Bktero]

Ce serait bien de nous dire ce qui ne va pas.... Je présume que tu es embêté par tout ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
gccw dvpez-void.c 
dvpez-void.c: In function ‘main’:
dvpez-void.c:65: warning: assignment makes integer from pointer without a cast
dvpez-void.c:76: warning: assignment makes integer from pointer without a cast
dvpez-void.c:78: error: expected expression before ‘]’ token
dvpez-void.c:78: error: incompatible type for argument 1 of ‘empiler’
dvpez-void.c:95: warning: passing argument 1 of ‘printf’ makes pointer from integer without a cast
dvpez-void.c:95: warning: format not a string literal and no format arguments
dvpez-void.c:95: warning: format not a string literal and no format arguments
dvpez-void.c:99: error: expected declaration or statement at end of input
dvpez-void.c:51: warning: unused variable ‘npi2’
dvpez-void.c:99: warning: control reaches end of non-void function

Quelques remarques :

• Note que tu peux utiliser p->champ de manière équivalente à (*p).champ. Beaucoup trouvent cette écriture plus simple.
  
• Pourquoi ne pas faire fonction pour initialiser la pile, cad dire remplir le champ taille et faire l'allocation ? Je n'ai d'ailleurs pas trouvé de réservation mémoire pour le champ t...
  

• Code :

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

  1
  2
  3
  oper = (char*)malloc(n*sizeof(char));
  i=0;
  while(oper[i] != '\0') {i++;}

  Au lieu du code ci-dessus, tu peux utiliser calloc() pour faire l'allocation et tout mettre à zéro. Tout malloc()/calloc() nécessite un free() à un moment.
  
• u=i;Pourquoi ne pas utiliser i pour faire l'allocation ? Surtout que tu ne te sers pas de u après.
  
• npi1.taille = (int*)malloc(u*sizeof(char));malloc() avec sizeof char, un cast en int*, le tout dans un champ de type int. Mais pourquoi ?
  
• Autant que possible, n'utilises pas ce qui se trouve dans conio.h. Ce fichier n'est disponible que sous Windows donc tu ne pourras pas utiliser ton code sous une autre plateforme. Utilise getchar plutôt que getch. http://man.developpez.com/man3/getchar.3.php
  
• npi1.sommet = NULL;Ce champ n'est pas un pointeur, tu ne peux pas lui donner la valeur NULL.

Dans l'ensemble, tu sembles totalement mélanger les différents champs de ta structure dans ta boucle, mets tes idées au clair puis reprend ta boucle et corrige les problèmes que tu découvriras. Regarde ce que te dis ton compilateur, il t'indique souvent que tu essayes de mettre une variable d'un type non attendu dans une opération.

Bon courage

[kwariz]

En plus des remarques de Bktero, il y quelques petites erreurs dans ton parsing.
Quand tu tombes sur un caractère qui n'est ni '*' ni '+' tu empiles la valeur ascii du caractère au lieu de parser un nombre et de l'empiler. Par exemple avec la chaîne 10 1 +, tu tombes sur le caractère '1', tu empiles un char et le sommet de ta pile contiendra 49 (qui est le code ascii du caractère 1).
Je ne vois pas dans ton code une incrémentation de i pour passer au caractère suivant, mais imaginons que tu passes au suivant.
Tu tombes sur '0' et du coup tu empiles 48 ... la valeur du code ascii de '0'.
Tu tombes sur ' ' (une espace) et du coup tu empiles 32 ... la valeur du code ascii de ' '.
Tu tombes sur '1' ... tu empiles 49
Tu tombes sur '+', tu dépiles deux fois tu additionnes et tu obtiens 49+32=81 que tu empiles
Tu tombes sur '\0' -> tu retournes 81 ....

L'idéal serait de

• quand tu tombes sur un caractère qui est un chiffre de lire un nombre (par exemple en utilisant strtol)
• quand tu tombes sur une espace ... l'ignorer
  Note que tu es obligée de traiter les espaces pour différencier 110 de 1 1 0 de 11 0 de 1 10 ...
• quand tu tombes sur un opérateur le traiter
• ne pas oublier de gérer les erreurs comme
  
  • que se passe-t-il si tu tombes sur un caractère comme '@' ?
    on peut aussi bien l'ignorer que de dire que l'expression contient une erreur
  • si la pile n'est pas assez remplie pour un opération ?
  • si la pile n'est pas vide à la fin ?
  • ...