Evaluation d'une expression arithmétique

[Romu']

Bonjour !

J'ai voulu créer un programme qui donne le résultat d'un calcul. Le calcul est donné sous forme d'une chaîne du type "3*2+1", "2*(8+5)" etc... . Le défi est de bien gérer les priorités.
Je suis venu poster le code que j'ai écrit, qui m'a tout l'air de fonctionner d'après mes tests.
Je suis preneur de toutes les remarques concernant le codage, et vous pouvez si vous le voulez aller chercher la petite bête (mais en me prévenant avant ;) ).

Note : si l'algorithme est faux, merci de ne pas me donner la correction ni même de me dire où est l'erreur ! Me donner un exemple qui le fait se tromper me suffit.

* Il y a peu de commentaires mais les noms sont je trouve assez explicites (_dl signifie "déjà lu").
* J'utilise des pointeurs pour les variables "G_dl" et "Op_dl" pour avoir une valeur signifiant "qu'il ne faut pas les utiliser" (NULL).
* La condition de la boucle se fait sur la variable "op", car en fait, elle peut contenir soit un opérateur, soir le caractère null de fin de chaîne, soit ')'.
Voici le code de la fonction elle-même :

Code:


double calculer_ (const char* calcul, double* G_dl, char* Op_dl, unsigned int prio_op_pre, const char** p_calcul) {
    double G, D; /* opérande de gauche et opérande de droite */
    char op, op_suivant;

    /* *** initialisations *** */
    /* Si G_dl est un pointeur valide */
    if (G_dl != NULL) {
        G = *G_dl;
    }
    else { /* Sinon on lit G */
        if (*calcul == '(')
            G = calculer_(calcul+1, NULL, NULL, 0, &calcul);
        else
            G = strtod(calcul, (char**)&calcul);
    }

    /* Si Op_dl est un pointeur valide */
    if (Op_dl != NULL) {
        op = *Op_dl;
    }
    else { /* Sinon on lit l'opérateur */
        op = *calcul;
        calcul++;
    }

    /* *** boucle des calculs *** */
    while (op != '\0' && op != ')' && priorite(op) > prio_op_pre) {
        /* Lecture de l'opérande de droite */
        if (*calcul == '(')
            D = calculer_(calcul+1, NULL, NULL, 0, &calcul);
        else
            D = strtod(calcul, (char**)&calcul);

        /* Opérateur suivant */
        op_suivant = *calcul;
        calcul++;

        if (est_oper(op_suivant) && priorite(op_suivant) > priorite(op)) {
            D = calculer_(calcul, &D, &op_suivant, priorite(op), &calcul);
        }

        G = effectuer_oper(G, op, D);
        op = op_suivant;
    }
    /* *** fin de la boucle des calculs *** */

    /* Mise à jour de l'opérateur suivant pour la fonction appelante */
    if (Op_dl != NULL)
        *Op_dl = op_suivant;

    /* A pour effet d'indiquer à la fonction appelante jusqu'où
        la fonction appelée a lu la chaine 'calcul' */
    if (p_calcul != NULL)
        *p_calcul = calcul;

    return G;
}


fonctions annexes :

Code:


/* Calcul de 'G op D' */
double effectuer_oper (double G, char op, double D) {
    double resultat = 0;

    switch (op) {
        case '+':
            resultat = G + D;
            break;
        case '-':
            resultat = G - D;
            break;
        case '*':
            resultat = G * D;
            break;
        default: /* '/' normalement */
            resultat = G / D;
    }

    return resultat;
}

/* Donne le nombre identifiant la priorité de l'opérateur donné */
unsigned int priorite (char op) {
    unsigned int prio = 0;

    switch (op) {
        case '+':
        case '-':
            prio = 1;
            break;
        case '*':
        case '/':
            prio = 2;
            break;
    }

    return prio;
}

/* Renvoie une valeur positive si 'op' est un opérateur géré. */
int est_oper (char op) {
    switch (op) {
        case '+': case '-': case '*': case '/':
            return 1;
        default:
            return 0;
    }
}


J'aimerais particulièrement éclaircir les points suivants :

• L'utilisation que je fais de strtod est-elle correcte (je veux en effet que 'calcul' pointe après le nombre lu) :
  

  Code:

  
/* calcul étant de type 'const char*' */
resultat = strtod(calcul, (char**)&calcul);


• Dans les fonctions annexes : j'ai pu lire plusieurs fois que -ed- conseille de ne mettre qu'un seul retour par fonction, d'où l'utilisation d'une variable dans les 2 premières, mais j'ai craqué dans la 3ième tellement il y avait peu de lignes. Mieux vaut quand même passer par une variable intermédiaire ? Je ferais mieux de n'utiliser qu'une seule méthode pour les 3 fonctions, mais laquelle au vu de leur simplicité ?
  

La chaîne représentant le calcul est supposée bien formatée : c'est comme on écrirait un calcul sur une feuille, mais sans les espaces, et avec '*' pour la multiplication et '/' pour la division.

La fonction s'appelle "calculer_" car pour éviter à l'utilisateur le passage des paramètres qui ne servent qu'au contrôle des fonctions appelées récursivement, j'ai écrit :

Code:


#define calculer(c) calculer_((c), NULL, NULL, 0, NULL)


Merci d'avance pour les remarques ;).
*croisant les doigts et espérant ne pas avoir laissé passé une erreur horrible !*

[-ed-]

J'ai voulu créer un programme qui donne le résultat d'un calcul. Le calcul est donné sous forme d'une chaîne du type "3*2+1", "2*(8+5)" etc... . Le défi est de bien gérer les priorités.

Ce que tu veux faire s'appelle" évaluer une expression".

C'est un travail assez complexe qui met en œuvre des techniques avancées utilisées par les interpréteurs et autres compilateurs. Ce n'est pas à la portée d'un débutant en programmation.

Je veux bien corriger ton code sur le plan du C, mais je ne connais pas les techniques officielles d'évaluation d'expres​sion(On voit ça en maitrise d'info, BAC+5...)

Ton code est éparpillé. Donne un exemple de code compilable.

[Romu']

C'est un travail assez complexe qui met en œuvre des techniques avancées utilisées par les interpréteurs et autres compilateurs. Ce n'est pas à la portée d'un débutant en programmation.

Il dois y avoir un truc qui m'échappe, mon programme donne le bon résultat à tous mes tests...

Je veux bien corriger ton code sur le plan du C

C'est exactement ce que je cherchais ;)

Ceci devrait compiler (un simple copier/coller dans code::blocks et tout va bien, chez moi en tout cas) :

Code:


#include <stdio.h>
#include <stdlib.h>

#define calculer(c) calculer_((c), NULL, NULL, 0, NULL)

double calculer_ (const char*, double*, char*, unsigned int, const char**);
double effectuer_oper (double, char, double);
unsigned int priorite (char);
int est_oper (char);

int main (void) {
    /* Un test quelconque */
    printf("%f\n", calculer("3*(5-2)+1"));
    return 0;
}

double calculer_ (const char* calcul, double* G_dl, char* Op_dl, unsigned int prio_op_pre, const char** p_calcul) {
    double G, D; /* opérande de gauche et opérande de droite */
    char op, op_suivant;

    /* *** initialisations *** */
    /* Si G_dl est un pointeur valide */
    if (G_dl != NULL) {
        G = *G_dl;
    }
    else { /* Sinon on lit G */
        if (*calcul == '(')
            G = calculer_(calcul+1, NULL, NULL, 0, &calcul);
        else
            G = strtod(calcul, (char**)&calcul);
    }

    /* Si Op_dl est un pointeur valide */
    if (Op_dl != NULL) {
        op = *Op_dl;
    }
    else { /* Sinon on lit l'opérateur */
        op = *calcul;
        calcul++;
    }

    /* *** boucle des calculs *** */
    while (op != '\0' && op != ')' && priorite(op) > prio_op_pre) {
        /* Lecture de l'opérande de droite */
        if (*calcul == '(')
            D = calculer_(calcul+1, NULL, NULL, 0, &calcul);
        else
            D = strtod(calcul, (char**)&calcul);

        /* Opérateur suivant */
        op_suivant = *calcul;
        calcul++;

        if (est_oper(op_suivant) && priorite(op_suivant) > priorite(op)) {
            D = calculer_(calcul, &D, &op_suivant, priorite(op), &calcul);
        }

        G = effectuer_oper(G, op, D);
        op = op_suivant;
    }
    /* *** fin de la boucle des calculs *** */

    /* Mise à jour de l'opérateur suivant pour la fonction appelante */
    if (Op_dl != NULL)
        *Op_dl = op_suivant;

    /* A pour effet d'indiquer à la fonction appelante jusqu'où
        la fonction appelée a lu la chaine 'calcul' */
    if (p_calcul != NULL)
        *p_calcul = calcul;

    return G;
}


/* Calcul de 'G op D' */
double effectuer_oper (double G, char op, double D) {
    double resultat = 0;

    switch (op) {
        case '+':
            resultat = G + D;
            break;
        case '-':
            resultat = G - D;
            break;
        case '*':
            resultat = G * D;
            break;
        default: /* '/' normalement */
            resultat = G / D;
    }

    return resultat;
}

/* Donne le nombre identifiant la priorité de l'opérateur donné */
unsigned int priorite (char op) {
    unsigned int prio = 0;

    switch (op) {
        case '+':
        case '-':
            prio = 1;
            break;
        case '*':
        case '/':
            prio = 2;
            break;
    }

    return prio;
}

/* Renvoie une valeur positive si 'op' est un opérateur géré. */
int est_oper (char op) {
    switch (op) {
        case '+': case '-': case '*': case '/':
            return 1;
        default:
            return 0;
    }
}


[-ed-]

C'est un travail assez complexe qui met en œuvre des techniques avancées utilisées par les interpréteurs et autres compilateurs. Ce n'est pas à la portée d'un débutant en programmation.

Il dois y avoir un truc qui m'échappe, mon programme donne le bon résultat à tous mes tests...

J'ai commencé à passer des tests unitaires...

Code:


#ifdef TEST
#include <assert.h>
#include <stdio.h>
#include <math.h>
#include <float.h>

/* http://delahaye.emmanuel.free.fr/clib/ */
#include "ed/inc/prt.h"

#define fcmp(a, b) (fabs(a - b) < DBL_EPSILON)

#define DBG 1

int main (void)
{
  assert (fcmp(calculer ("0"), 0) == 1);
  assert (fcmp(calculer ("0 + 0"),  0)== 1);
  assert (fcmp(calculer ("0 - 0"),  0)== 1);
  assert (fcmp(calculer ("0 * 0"),  0)== 1);
  assert (fcmp(calculer ("0 / 0"),  0)== 1);

  assert (fcmp(calculer ("1"),  1)== 1);
  assert (fcmp(calculer ("1 + 0"),  1)== 1);
  assert (fcmp(calculer ("1 - 0"),  1)== 1);
#if !DBG
  assert (fcmp(calculer ("1 * 0"),  0)== 1);
  assert (fcmp(calculer ("1 / 0"),  0)== 1);
#else
  PRT_D(calculer ("1 * 0"));
  PRT_D(calculer ("1 / 0"));
#endif

  assert (fcmp(calculer ("1 + 1"),  1)== 1);
#if !DBG
  assert (fcmp(calculer ("1 - 1"),  0)== 1);
#else
  PRT_D(calculer ("1 - 1"));
#endif
  assert (fcmp(calculer ("1 * 1"),  1)== 1);
  assert (fcmp(calculer ("1 / 1"),  1)== 1);

#if !DBG
  puts("P A S S E D");
#endif
  return 0;
}

#endif


Je constate quelques anomalies...

Code:


calculer ("1 * 0") = 1.00
calculer ("1 / 0") = 1.00
calculer ("1 - 1") = 1.00

Process returned 0 (0x0)  execution time : 0.026 s
Press any key to continue.


D'autre part, 0/0 ne devrait pas donner un résultat valide (indéfini)...

[-ed-]

Je veux bien corriger ton code sur le plan du C

C'est exactement ce que je cherchais ;)

- Inutile de définir des prototypes ici. des fonctions privées (static) correctement disposées suffisent.

A part ça, je n'ai pas grand chose à dire sur le codage lui même qui est correct... sauf que certains résultats sont faux. Il faut multiplier les tests unitaires, j'ai ouvert la voie...

[Romu']

Je constate quelques anomalies...
[...]
D'autre part, 0/0 ne devrait pas donner un résultat valide (indéfini)...

Il ne faut pas d'espace dans la chaîne : il faut écrire, par exemple, "1*1" et non pas "1 * 1".
strtod retournant une valeur utilisable même en cas d'erreur et un opérateur étant pris par défaut (la division), le fait que l'erreur vienne des espaces n'est pas très facile à voir. Je ferais si j'y arrive une fonction vérifiant la syntaxe plus tard.

calculer("1/0") affiche chez moi (avec %f pour printf) "1.#INF00". Je préfère laisser à l'utilisateur de la fonction le soin de tester errno pour savoir s'il y a eu un problème. Le faire dans la fonction elle-même me parait trop compliqué car, difficile de sortir de fonctions qui sont imbriquées potentiellement beaucoup de fois.

[-ed-]

Je constate quelques anomalies...
[...]
D'autre part, 0/0 ne devrait pas donner un résultat valide (indéfini)...

Il ne faut pas d'espace dans la chaîne : il faut écrire, par exemple, "1*1" et non pas "1 * 1".

Première nouvelle... Une petite fonction de nettoyage de blancs ne serait pas inutile...

strtod retournant une valeur utilisable même en cas d'erreur et un opérateur étant pris par défaut (la division), le fait que l'erreur vienne des espaces n'est pas très facile à voir. Je ferais si j'y arrive une fonction vérifiant la syntaxe plus tard.

Il faut blinder ça tout de suite. strtod() permet un contrôle notamment avec le 2 ème paramètre. Il met aussi à jour errno en cas d'erreur (E je ne sais plus quoi) ou de dépassement (ERANGE)

calculer("1/0") affiche chez moi (avec %f pour printf) "1.#INF00". Je préfère laisser à l'utilisateur de la fonction le soin de tester errno pour savoir s'il y a eu un problème. Le faire dans la fonction elle-même me parait trop compliqué car, difficile de sortir de fonctions qui sont imbriquées potentiellement beaucoup de fois.

Je n'en savais rien...

Ceci fonctionne correctement :

Code:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* Calcul de 'G op D' */
double effectuer_oper (double G, char op, double D)
{
  double resultat = 0;

  switch (op)
  {
  case '+':
      resultat = G + D;
      break;
  case '-':
      resultat = G - D;
      break;
  case '*':
      resultat = G * D;
      break;
  default:                    /* '/' normalement */
      resultat = G / D;
  }

  return resultat;
}

/* Donne le nombre identifiant la priorité de l'opérateur donné */
unsigned int priorite (char op)
{
  unsigned int prio = 0;

  switch (op)
  {
  case '+':
  case '-':
      prio = 1;
      break;
  case '*':
  case '/':
      prio = 2;
      break;
  }

  return prio;
}

/* Renvoie une valeur positive si 'op' est un opérateur géré. */
int est_oper (char op)
{
  switch (op)
  {
  case '+':
  case '-':
  case '*':
  case '/':
      return 1;
  default:
      return 0;
  }
}

double calculer_r (const char *calcul, double *G_dl, char *Op_dl,
                  unsigned int prio_op_pre, const char **p_calcul)
{
  double G, D;                /* opérande de gauche et opérande de droite */
  char op, op_suivant;

  /* *** initialisations *** */
  /* Si G_dl est un pointeur valide */
  if (G_dl != NULL)
  {
      G = *G_dl;
  }
  else
  {                            /* Sinon on lit G */
      if (*calcul == '(')
        G = calculer_r (calcul + 1, NULL, NULL, 0, &calcul);
      else
        G = strtod (calcul, (char **) &calcul);
  }

  /* Si Op_dl est un pointeur valide */
  if (Op_dl != NULL)
  {
      op = *Op_dl;
  }
  else
  {                            /* Sinon on lit l'opérateur */
      op = *calcul;
      calcul++;
  }

  /* *** boucle des calculs *** */
  while (op != '\0' && op != ')' && priorite (op) > prio_op_pre)
  {
      /* Lecture de l'opérande de droite */
      if (*calcul == '(')
        D = calculer_r (calcul + 1, NULL, NULL, 0, &calcul);
      else
        D = strtod (calcul, (char **) &calcul);

      /* Opérateur suivant */
      op_suivant = *calcul;
      calcul++;

      if (est_oper (op_suivant) && priorite (op_suivant) > priorite (op))
      {
        D = calculer_r (calcul, &D, &op_suivant, priorite (op), &calcul);
      }

      G = effectuer_oper (G, op, D);
      op = op_suivant;
  }
  /* *** fin de la boucle des calculs *** */

  /* Mise à jour de l'opérateur suivant pour la fonction appelante */
  if (Op_dl != NULL)
      *Op_dl = op_suivant;

  /* A pour effet d'indiquer à la fonction appelante jusqu'où
      la fonction appelée a lu la chaine 'calcul' */
  if (p_calcul != NULL)
      *p_calcul = calcul;

  return G;
}

char *str_dup (char const *s)
{
  char *sdup = NULL;
  size_t size = strlen (s) + 1;
  if (size > 1)
  {
      sdup = malloc (size);
      if (sdup != NULL)
      {
        memcpy (sdup, s, size);
      }
  }
  return sdup;
}

void str_nospace (char *s)
{
  char *r = s;
  char *w = s;

  while (*r != 0)
  {
      if (!isspace (*r))
      {
        *w = *r;
        w++;
      }
      r++;
  }
  *w = 0;
}

double calculer (const char *calcul)
{
  double val = 0;
  char *sdup = str_dup (calcul);
  if (sdup != NULL)
  {
      str_nospace (sdup);
      val = calculer_r (sdup, NULL, NULL, 0, NULL);
      free (sdup);
  }
  return val;
}

#ifdef TEST
#include <assert.h>
#include <stdio.h>
#include <math.h>
#include <float.h>

/* http://delahaye.emmanuel.free.fr/clib/ */
#include "ed/inc/prt.h"

#define fcmp(a, b) (fabs(a - b) < DBL_EPSILON)

#define DBG 1

#define SIND "-1.#IND00"
#define SINF "1.#INF00"

int main (void)
{
  assert (fcmp (calculer ("0"), 0) == 1);
  assert (fcmp (calculer ("0 + 0"), 0) == 1);
  assert (fcmp (calculer ("0 - 0"), 0) == 1);
  assert (fcmp (calculer ("0 * 0"), 0) == 1);

  {
      char s[32];
      sprintf (s, "%f", calculer ("0 / 0"));
      assert (strcmp (s, SIND) == 0);
  }

  assert (fcmp (calculer ("1"), 1) == 1);
  assert (fcmp (calculer ("1 + 0"), 1) == 1);
  assert (fcmp (calculer ("1 - 0"), 1) == 1);
  assert (fcmp (calculer ("1 * 0"), 0) == 1);
  {
      char s[32];
      sprintf (s, "%f", calculer ("1 / 0"));
      assert (strcmp (s, SINF) == 0);
  }

  assert (fcmp (calculer ("1 + 1"), 2) == 1);
  assert (fcmp (calculer ("1 - 1"), 0) == 1);
  assert (fcmp (calculer ("1 * 1"), 1) == 1);
  assert (fcmp (calculer ("1 / 1"), 1) == 1);

#if !DBG
  puts ("P A S S E D");
#endif
  return 0;
}

#endif


Tu remarqueras que j'ai remplacé la macro d'appel par une fonction. La fonction récursive est suffixée _r. C'est une pratique courante et claire. Elle pourrait être privée (static).

[Romu']

Première nouvelle... [...]

J'avais écrit ceci à la fin de mon premier post :

La chaîne représentant le calcul est supposée bien formatée : c'est comme on écrirait un calcul sur une feuille, mais sans les espaces, et avec '*' pour la multiplication et '/' pour la division.

A votre décharge la forme est peut-être défaillante ;).


Après votre réflexion sur le fait que ce genre de programmes soient très difficiles à réaliser, je suis allé traîner sur quelques autres forums pour voir ce qu'on pouvait y lire, ou si on pouvait me donner des chaînes "pièges" à tester.
Il en est ressorti que finalement, c'est pas si difficile. Alors je suis complètement perdu ! Que penser ?

• Soit je ne suis plus un programmeur débutant
  
• Soit on s'est mal compris
  
• Soit vous avez surestimé la difficulté
  
• Soit il y a néanmoins une erreur dans l'algorithme
  

L'avenir le dira...

Merci bien en tout cas !

[woolfmother]

Programme efficace, chapeau.. Chez moi juste un petit soucis avec 0*-0 n'est pas égal à la tête à toto.. mais -0.000.. au lieu de 0.

Sinon c'est très brillant en effet.

Petit détail : je conseille l'utilisation de

Code:


int main(int argc, char **argv) {
    /* Un test quelconque */
    printf("%f\n", calculer(argv[1]));
    return 0;
}

pour pouvoir utiliser la ligne de commande; ex:

Code:

 $ prog.out "4*4-3+2"

nb : penser à ne pas oublier les "" dans BASH sous Linux sinon pb avec le signe / et * avec les parenthèses..

[Contenu sponsorisé]