algo chaine de caractere en int

Bonjours à tous !
Je travail actuellement sur un algo qui permet de convertir une chaine de caractère,passée en paramètre de ma fonction ex: "1234", en int.
Je dois retourner seulement les nombres et vérifier le '+' et '-'
(pas de atoi ni strol possible)
Voila le debut de ma fonction :

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
int     getnombre(char *str)
{
        int     i;
        int     *res;
 
        res = 0;
        for (i = 0; str[i] != '\0'; i++)
          {
                //test si le 1er caractere n est pas un nombre                                                                           
                if (str[0] < '0' || str[0] > '9')
                {
                        return (0);
 
                }
                //test si c est negatif                                                                                                      
                else if (str[0] == '-')
		{
 
                }
                else
                {
                        res = (int)(str[i] - '0');
                }
          }
        return (res);
}

Je bloque sur comment retourner les les nombres dans l'ordre...

Bonjour,

A mon avis tes vérifications sont dans le mauvais ordre... Il faut que tu vérifies d'abord le signe et ensuite si le 2eme caractère est un nombre car si tu as "-1" tu vas rentrer dans ta 1er condition et sortir de ta boucle.

Ensuite pour faire ce genre d'exercice il faut que t'identifies le signe de ton nombre en 1er. Ensuite pour le récupérer tu procède de cette manière (avec une boucle et quelques conditions ça devrait le faire) :

- Tu récupères la valeurs ASCII du 1er caractère et tu lui enlèves 48.

- Si ta chaine de caractère n'est pas finie tu multiplies le nombre que tu as par 10.

- Tu récupères la valeurs ASCII du 2eme caractère et tu lui enlèves 48.

- Tu ajoutes le chiffre que tu viens de trouver à ton nombre.

- Si ta chaine de caractère n'est pas finie tu multiplies le nombre que tu as par 10.

- Et ainsi de suite.

- Puis tu appliques le signe à ton nombre.

Après je sais pas si t'as des exemples de ce style à gérer : "--+-+-1684" ou encore des nombres qui sortent de la taille d'un int...

Je te laisse coder si tu as des problèmes avec cet algo poste ton code et dis nous les erreurs et problèmes que tu rencontres.

Je dois aussi gérer les multiples occurrences et les nombres aux qui sortent d'un int

Dans ton 1er poste tu dis vouloir :

Citation:

Je travail actuellement sur un algo qui permet de convertir une chaine de caractère,passée en paramètre de ma fonction ex: "1234", en int.

et ensuite tu dis cela

Citation:

Je dois aussi gérer les multiples occurrences et les nombres aux qui sortent d'un int

Décris nous les chaîne de caractères que tu peux avoir (les cas extrême).

Bonjour,

tu peux essayer d'implémenter un automate du genre :

http://i47.tinypic.com/15ojmfk.png

Bonjour,

je me suis amusé à implémenter une fonction robuste pour lire un entier (type int). L'automate s'implémente assez facilement en suivant un algo dont le squelette ressemblerait à :
Code:

1 2 3 4 5 6 7 8 9 10 tant qu'on a un signe + ou - si c'est - alors on change le signe final du nombre nombre=0 tant qu'on a un chiffre nombre = nombre x 10 + chiffre si on a autre chose que la fin de la chaine alors renvoyer une erreur
On peut étoffer tout ça avec une gestion de l'overflow.

Pour coder ça on va avoir besoin d'un code de retour pour dire :
* tout c'est bien passé, la chaine ne contenait qu'un int valide
* on a rencontré un caractère invalide
* tout se passait bien, mais si on continuait on obtenait un entier qui ne tenait pas dans un int : overflow
* on nous a passé NULL comme chaine à traiter ! (bon spécifique à c)

Ce serait pas mal aussi que si on le désire on puisse obtenir l'endroit où on c'est arrêté (la fon de la chaine ou le caractère invalide ou le chiffre qui provoque l'overflow)

Un prototype pourrait être :

Code:

pi_res_t parse_int(char* str, int* integer, char** ptr);

str étant la chaine à parser
integer pointant vers la variable user qui va recevoir ce qu'on parse
ptr un pointeur sur un pointeur de char qui s'il n'est pas nul pointera vers le premier caractère non traité
le retour pi_res_t sera un enum pour différencier les différents cas vu plus haut

Code:

typedef enum {PI_OK, PI_ERANGE, PI_EOVERFLOW, PI_ENULLARG} pi_res_t;

PI_OK : tout c'est bien passé
PI_ERANGE : on a rencontré un caractère invalide
PI_EOVERFLOW : le traitement du chiffre suivant provoque un overflow
PI_ENULLARG : str vaut NULL !

En gros on l'utiliserait ainsi :
Code:

1 2 3 4 5 char* test="--16384!" char* ptr_premier_car_non_traite=NULL; int integer; pi_res_t res; res =parse_int(test,&integer, &ptr_premier_char_non_traite);
Dans ce cas, res contiendrait PI_ERANGE (car le ! n'est pas un caractère valide)
integer vaudrait 16384 (on retourne quand même ce qu'on a pu parser)
et ptr_premier_char_non_traite pointerait vers ce fameux '!' dans test, en particulier ptr_premier_char_non_traite - test donne la position de ce caractère.
Si on n'a pas besoin de cette information on peut passe NULL pour en avertir la fonction :

Code:

res=parse_int(test&integer,NULL)

Tout est identique sauf qu'on a pas d'info sur où se trouve ce caractère.

Passons à l'implémentation:

La première partie de notre fonction est super simple : si on nous passe une chaine NULL on s'arrête de suite :
Code:

1 2 3 4 5 6 if (str==NULL) { if (endchar!=NULL) *endchar=NULL; *integer=0; return PI_ENULLARG; }
Classique ... on convient juste que si on nous donne NULL, alors on renvoie l'entier 0, si l'utilisateur désire savoir où ça plante on lui renvoie NULL et la fonction elle même renvoie le code adéquat.

Passons aux choses sérieuse en commençant par un petit détour concernant la gestion de l'overflow. En c, un int 32bits peut représenter les entier de - 2^(31) = -2147483648 jusqu'à 2^(31)-1 = 2147483647. Un int non signé quant à lui peut représenter les entiers de 0 à 4294967295 = (2^32-1).
On va poser MAXINTPOS=2147483648.

Comme nous parsons le signe indépendemment du nombre, nous pouvons utiliser un booléen pour indiquer le signe du nombre parsé, puis construire un nombre positif sachant que le résultat final sera ce nombre fois le signe parsé (+1 ou -1).
Nous allons donc utiliser des entiers non signés et vérifier lors de la construction du nombre que ce nombre est bien représentable comme un int. Nous vérifions d'abord si l'opération elle-même n'a pas provoqué un overflow sur les entiers non signés (1), puis si ce nombre peut être représenté avec un int (2) :
(1) : avec a et b non signés, a=b*10 provoque un overflow si b est différent de a/10 (ok ... je n'en suis pas sûr, c'est à prouver voire à remplacer par quelquechose de plus simple)
(2) : a non signé, a n'est représentable avec un int si a>=MAXINTPOS, respectivement -a ne l'est pas si a>MAXINTPOS

ok, donc dans la suite nous aurons besoin de :
Code:

1 2 3 4 5 6 char* ptr=str; unsigned int number=0; unsigned int tmp_number; unsigned char digit; int is_neg=0; int overflow=0;
ptr sera le pointeur sur le caractère en cours de traitement
tmp_number le résultat intermédiaire nous permettant de vérifier s'il y a eu un overflow ou non
digit la valeur décimale du caractère
is_neg le booléen indiquant si on parse un entier positif ou négatif
overflow le booléen qui indique si on a eu un overflow pendant la conversion

On aura aussi au préalable définit notre MAXINTPOS, par exemple :

Code:

#define MAXINTPOS ((unsigned int) (1<<(sizeof(int)*8-1)))

La première tâche est donc de traiter le signe :
Code:

1 2 3 4 5 while ( (*ptr=='-') || (*ptr=='+') ) { if (*ptr=='-') is_neg=!is_neg; ++ptr; }
Rien de particulièrement difficile : on change le signe si on rencontre un '-'.
Soit on ne rentre pas dans la boucle (il n'y a pas de signe), soit on rentre (car il y a au moins un signe) et quand on en ressort il y autre chose qu'un signe.

On peut donc embrayer sur la construction du nombre, j'ai essayé de bien la détailler. Tant qu'on trouve des chiffres et qu'il n'y a pas eu d'overflow, on lit le chiffre, on construit temporairement le nombre que ça donnerait s'il n'y a pas d'overflow c'est ok sinon on sort immédiatement.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 while ( (*ptr>='0') && (*ptr<='9') && (!overflow) ) { digit=*ptr - '0'; tmp_number=number*10+digit; if ( ( ((tmp_number-digit)/10)!=number) || ( ( is_neg) && (tmp_number>MAXINTPOS) ) || ( (!is_neg) && (tmp_number>MAXINTPOS-1) ) ){ overflow=1; } else { number=tmp_number; ++ptr; }
Voilà donc en sortant de cette boucle (si on y est rentré) on est certain d'avoir parsé un nombre qui entre dans un int. Si overflow vaut 1, il nous reste des chiffres dans le buffer mais on ne peut aller plus loin car sinon ça ne tient plus dans un int, sinon soit le caractère est '\0' dans ce cas tout est ok, soit c'est autre chose et on a un caractère invalide.

Si on ne rentre pas dans cette boucle c'est qu'on a pas à faire à un nombre. Le plus simple savoir si on y est rentré est de soit mettre inconditionnellement un booléen à 1 dans le boucle, ou de comparer le pointeur ptr avant et après la boucle pour savoir si on a avancé. Choisissons la seconde solution :
Code:

1 2 char *before_num_parse=ptr; while ( (*ptr>='0') && (*ptr<='9') && (!overflow) ) {
Donc après cette boucle, soit before_num_parse==ptr et dans ce cas il n'y a pas de nombre : on renvoie 0 avec une erreur sur caractère invalide,
soit les pointeurs sont différents et on a bien un nombre, dans ce cas on renvoie ce nombre multiplié par le signe transformé en int , s'il y a eu overflow on renvoie l'erreur overflow, si le dernier caractère n'est pas '\0' on renvoie une erreur carcatère invalide et sinon tout est bon.
Mais dans tous les cas de figure, si l'utilisateur veut s'avoir où on s'arrête on peut lui dire.
Ce qui donne :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 if (endchar!=NULL) *endchar=ptr; if (before_num_parse==ptr) { *integer = 0; return PI_ERANGE; } else { if (is_neg) *integer=- (int)number; else *integer= (int)number; if (overflow) return PI_EOVERFLOW; else if (*ptr!=0) return PI_ERANGE; else return PI_OK; }
Bon ... tout y est :)

C'est le type d'exercice qui se complique si on cherche à trouver une solution robuste.
Cette fonction n'est pas sensible aux attaques de type buffer overflow, elle prend en compte tous les cas de figure et permet à l'utilisateur d'agir en conséquence en cas d'erreur.
On peut évidemment étendre cette fonction pour qu'elle accepte les caractères d'espacement facilement, pour pouvoir parser des entiers signés plus longs (long et long long, avec peut-être une restriction au niveau du check des overflows). On peut aussi l'étendre avec une fonctionnalité du type try parse en autorisant un pointeur sur int est NULL par exemple.

Je vais poster le code complet dans la section source avec un petit jeu d'essai. Je ne commente pas le code (je sais honte sur moi!) mais j'y ajouterai un lien vers cette discussion.

Je suis ouvert à tout commentaire ou correction :)

sources disponibles ici : sources C

Tout d'abord, béni sois-tu pour cette réponse bien rédigée et pour ce code que tu as bien voulu nous partager aujourd'hui. La fonction a l'air de bien faire ce qu'elle est censée faire, du point de vue algorithmique, mais j'ai toutefois quelques remarques sur son écriture en C.

Citation:

pi_res_t parse_int(char* str, int* integer, char** ptr);

Je propose parse_int(const char* str, int* integer, const char** ptr), afin de pouvoir passer une chaîne littérale à la fonction.

Citation:

char* test="--16384!";

const char *. Sur les systèmes d'exploitations usuels, les chaînes littérales sont rangées dans des zones mémoire en lecture seule. Il faut donc les traiter comme des constantes.

Citation:

#define MAXINTPOS ((unsigned int) (1<<(sizeof(int)*8-1)))

Premièrement, je ne comprends pas le choix du nom de cette macro. Pourquoi MAXINTPOS ? C'est quoi le POS.
Deuxièmement, utiliser 8 pour représenter un byte n'est pas portable. Il vaut mieux utiliser CHAR_BITS (<limits.h>)
Et enfin, c'est déjà défini dans les en-têtes standards : INT_MAX. Toujours <limits.h> ;).

Au delà de ces quelques petites remarques, c'est vraiment du bon boulot.

A noter tout de même que c'est plus ou moins ce que les strtol et compagnie font (<stdlib.h>). Mais le but ici était de les réimplémenter, on est bien d'accord.

1 pièce(s) jointe(s)

Citation:

Envoyé par Melem

Tout d'abord, béni sois-tu pour cette réponse bien rédigée et pour ce code que tu as bien voulu nous partager aujourd'hui. La fonction a l'air de bien faire ce qu'elle est censée faire, du point de vue algorithmique, mais j'ai toutefois quelques remarques sur son écriture en C.

Je suis tout ouïe :)

Citation:

Envoyé par Melem

Je propose parse_int(const char* str, int* integer, const char** ptr), afin de pouvoir passer une chaîne littérale à la fonction.

const char *. Sur les systèmes d'exploitations usuels, les chaînes littérales sont rangées dans des zones mémoire en lecture seule. Il faut donc les traiter comme des constantes.

OK, j'ai apporté les modifications nécessaires pour str. En revanche pour ptr je ne pense pas rajouter le const puisque je vais modifier le contenu de *ptr si le paramètre n'est pas NULL.

Citation:

Envoyé par Melem

Premièrement, je ne comprends pas le choix du nom de cette macro. Pourquoi MAXINTPOS ? C'est quoi le POS.
Deuxièmement, utiliser 8 pour représenter un byte n'est pas portable. Il vaut mieux utiliser CHAR_BITS (<limits.h>)
Et enfin, c'est déjà défini dans les en-têtes standards : INT_MAX. Toujours <limits.h> ;).

POS pour positif, ok ça fait un peu radin d'avoir tronqué le ITIVE :)
J'ai modifié le code en renommant le define en MAX_POSITIVE_INT et en utilisant CHAR_BIT.
En fait je n'ai pas réutilisé INT_MAX parce que ça ne m'est pas venu à l'idée :)

Citation:

Envoyé par Melem

Au delà de ces quelques petites remarques, c'est vraiment du bon boulot.

A noter tout de même que c'est plus ou moins ce que les strtol et compagnie font (<stdlib.h>). Mais le but ici était de les réimplémenter, on est bien d'accord.

Oui, ce n'est qu'un exemple d'implémentation, je ne prétends pas avoir trouvé le Graal du strtoi :)
Je mets les sources à jour.

Citation:

Envoyé par kwariz

En revanche pour ptr je ne pense pas rajouter le const puisque je vais modifier le contenu de *ptr si le paramètre n'est pas NULL.

Mais dans ce cas *ptr pointera sur un caractère de la chaîne parsée, qui peut pourtant être constante. Or déclarer const char **ptr ne t'empêchera pas de lui passer un char **, ce que tu aimerais sans doute faire les fois que tu passes une chaîne modifiable à str. Certes, strtol elle-même est déclarée avec char **endptr, mais la lib C n'est pas parfaite :) (gets, int size dans fgets, FILE * en dernier argument dans fread et fwrite, etc.)

Je n'y ai jamais cherché à comprendre profondément la vraie nature du const. J'ai, peut-être à tort, pris l'habitude de voir le const char* (ou autre const pointeur) comme un engagement. Si dans la déclaration de la fonction je vois const char* alors je sais que la chaine que je passe en paramètre ne sera pas modifiée, je le traduis plus ou moins implicitement par cette chaine est en read only pour la fonction. Alors qu'une chaine passée sans const signale que la fonction ne prend pas l'engagement de ne pas modifier la chaine.
C'est pourquoi je suis un peu réticent à rajouter le const. La chaine passée peut-être une chaine constante ou pas, je ne cherche pas à renvoyer un pointeur sur un pointeur sur un carcatère constant (car il ne pourrait pas l'être) c'est à l'utilisateur de la fonction de prendre ses responsabilités.

De manière équivalente une fonction qui retourne un const char* est pour moi une manière de dire implicitement "je renvoie une chaine mais tu n'est pas autorisé à faire un free dessus", alors qu'une fonction qui retourne un char* est pour moi le contrat "je te renvoie une chaine, à ta charge de faire le free". Mais là je m'égare un peu.

Quoique ... il y a de bonnes pratiques à ce sujet ?

Tu peux voir const comme un engagement, mais cela implique néanmoins une chose : la fonction pourra accepter des données const comme des données non const, puisqu'elles seront de toute façon traitées comme des const dans la fonction. Sans const, on ne pourra pas passer des données const. Conclusion, il est recommandé de toujours utiliser const sauf lorsque la fonction pourrait être amenée à modifier les données.

Ainsi par exemple, avec pi_res_t parse_int(const char* str, int* integer, const char** ptr);, tu pourras effectuer les appels suivants :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 const char *end; /* const obligatoire car on va parser une chaine constante */ parse_int("...", &n, &end); --- const char s[] = "..."; const char *end; /* const obligatoire car on va parser une chaine constante */ parse_int(s, &n, &end); --- char s[] = "..."; const char *end; /* const volontaire car on ne cherche pas a modifier *end par la suite */ parse_int(s, &n, &end); --- char s[] = "..."; char *end; /* Pas de const car on veut eventuellement modifier *end par la suite */ parse_int(s, &n, &end); --- etc.
Moins tu auras de const, moins tu auras de possibilités. Ici par exemple, en retirant le const du 3ème argument, tu n'auras droit qu'au dernier cas d'utilisation.

La fonction est utilisable dans les trois cas, seuls les messages à la compilation changent (dans tous les cas de figures).
Le premier paramètre en const char* ne pose pas de problème en soi, car si on lui donne un char* il y a une conversion implicite, qui correspond à ce qu'on veut. Mais ce n'est pas le cas pour le second, il n'y a pas de conversion explicite d'un char** vers const char**, donc il y a forcément des warnings émis lors de la compilation, non ?

Citation:

Envoyé par kwariz

La fonction est utilisable dans les trois cas

Oui désolé. Quand je disais que l'on ne pouvait pas utiliser la fonction dans les autres cas, je parlais en termes de bonnes pratiques. Pas que ça ne pouvait pas se faire techniquement.

Citation:

Envoyé par kwariz

seuls les messages à la compilation changent (dans tous les cas de figures).

Mais il ne faut pas minimiser ces messages. Ici le message qu'on obtiendra dans tous les cas sera "suppression de l'attribut const". Et c'est quelque chose de très mauvais. On peut alors ajouter un cast pour taire le compilateur, mais à ce moment là on a juste décidé d'ignorer le problème. On ne l'a pas résolu. Voir signature de Médinoc :D.

Citation:

Envoyé par kwariz

pour le second [cas], il n'y a pas de conversion explicite d'un char** vers const char**, donc il y a forcément des warnings émis lors de la compilation, non ?

Oui, mais ici il s'agit d'un warning "mineur" si on peut le dire : pas de conversion implicite de char ** vers const char **. En clair, cette conversion requiert un cast explicite. Tout simplement.