Cum ati implementa functia atoi()?

[0ptr]

Sa zicem ca sunteti la un interviu si vi se cere sa scrieti codul ce implementeaza functia C int atoi(const char* pChar).
Care ar fi implementarea voastra?

[cristianamarie]

http://www.koders.com/c/fidFA8C29887FD8 ... x?s=atoi.c (atoi)
http://www.koders.com/c/fidD928DC19C0D8 ... x?s=atoi.c (strtol)

[0ptr]

Cristi, multumesc pentru solutiile propuse. Singurul comentariu ar fi faptul ca sunt foarte mari sanse ca un interievator sa nu accepte prima varianta daca el urmareste sa vada cum gandesti.
Astept cu interes si alte variante. Take it as a game!

[cristianamarie]

Prima era doar link spre a doua, unde e implementarea
Dar nu ar trebui sa fie prea greu, tot number *= digit (base) se face. Cred ca aici conteaza edge cases (LIMIT_MAX etc), detectia de numere incorecte, error handling etc.

[Silviu Ardelean]

Eu propun urmatoarea implementare:

Code: Select all

int atoi(const char *pChar)
{
	int ret_val = 0, length = 0;
	bool isNegative =  (*pChar == '-') ? true : false;

	if (!isNegative && (*pChar < '0' || *pChar > '9'))
		return 0;

	while (*pChar != '\0')
	{
		if ((isNegative && length == 1 && (*pChar != '-') && (*pChar < '0' || *pChar > '9')) ||
			(length > 0 && (*pChar < '0' || *pChar > '9'))) // invalid char inside of string
				break;

		length++;
  	    pChar += sizeof(char);   // [sic] - remains for wide - char
	} 

	bool isFirst = false;	
	int decimal = 0;

  // simple way:  pChar -= length; 
	while (length > 0)
	{
		decimal = 1;
		if (isNegative) 
		{
			if (!isFirst)
			{
				length--;
				if (0 == length)
					break;
			}

			isFirst = true;
		}

		for (int i = 1; i < length; i++)
			decimal *= 10;

                
		ret_val +=   decimal * (int(*(pChar - length) - '0') % 10);	// maybe to much pointers arithmetics ;) just for fun
		length--;
	}

	if (isNegative)
		ret_val *= -1;

	return ret_val;
}

[patrujdoi]

Code: Select all

   while (length > 0)
   {
      decimal = 1;
      if (isNegative) 
      {
         if (!isFirst)
         {
            length--;
            if (0 == length)
               break;
         }

         isFirst = true;
      }

      for (int i = 1; i < length; i++)
         decimal *= 10;

      ret_val +=   decimal * (int(*(pChar - length) - '0') % 10);      
      length--;
   }

e cam prea quadratic ca sa fie nice.
Si nu accepta, nici spatii la inceputul. Si nu verifica over/underflow, nici NULL.
Si mai e si un loop de 'verificare' la inceput.
Si mai baga si un modulo pe acolo care la uC e moartea.

Eu zic ceva de genul (chiar daca nu e perfect):

Code: Select all

int my_atoi(const char *pChar)
{
	int sign = 1;
	int result = 0;
	unsigned char isFirst = 1;

	if (pChar != NULL)
	{
		while ((*pChar) && isspace(*pChar))
		{
			pChar++;
		}

		while (*pChar)
		{
			if ((*pChar == '-') || (*pChar == '+'))
			{
				if (isFirst)
				{
					sign = (*pChar == '-') ? -1 : 1;
				}
				else
				{
					result = 0;
					break;
				}
			}
			else
			{
				unsigned char digit = *pChar - '0';
				if (digit >= 10)
				{
					result = 0;
					break;
				}
				else
				{
					int lastVal = result;
					result *= 10;
					result += digit;

					if (result < lastVal)
					{
						result = (sign < 0) ? INT_MIN : INT_MAX;
						break;
					}
				}
			}

			isFirst = 0;
			pChar++;
		}

		// apply sign if we walked over the complete string
		if (*pChar == 0)
		{
			result *= sign;
		}
	}

	return result;
}

[0ptr]

Baieti, multumesc. Sunt interesante ambele abordari. Sunt deschis si la alte variante.

Si nu verifica over/underflow, nici NULL.

Aceste aspecte sunt ultimul lucru la care se uita un interievator (daca chiar se uita...). Ideea unui altfel de test e cu totul alta.

[Silviu Ardelean]

@patrujdoi pardon Mihnea defunct Dark: nu are nimeni pretentia variantei perfecte... Dar pentru ca iti place analiza, am si eu niste comentarii.

Si nu accepta, nici spatii la inceputul.

E o observatie pertinenta, dar si rezolvarea ta e incompleta.
Degeaba ai apelat la prietena isspace() caci si varianta ta intoarce 0 pentru un buffer ce contine litere:

Code: Select all

char szC[10] = {0};
strcpy(szC, "  -100m12");

Si mai e si un loop de 'verificare' la inceput.

Se pare ca nu ai inteles ideea abordata de mine. Loop-ul ala e un 'strlen()' mai special care ma ajuta ca functia mea sa intoarca la fel ca originala: -100 (daca nu exista spatii in avans).

Code: Select all

char szC[10] = {0};
strcpy(szC, "-100m12");

Varianta ta intoarce 0.

[Ovidiu Cucu]

...sunt foarte mari sanse ca un interievator sa nu accepte prima varianta daca el urmareste sa vada cum gandesti.
Astept cu interes si alte variante. Take it as a game!

Intreadevar sunt mari sanse ca un interievator sa fie cu pluta pe Bahlui in ce priveste C-ul.
In standard scrie ceva de genul:

7.20.1.2 The atoi, atol, and atoll functions
[...]
Except for the behavior on error, they are equivalent to
atoi: (int)strtol(nptr, (char **)NULL, 10)
atol: strtol(nptr, (char **)NULL, 10)
atoll: strtoll(nptr, (char **)NULL, 10)

"Need more? Ok then, please give me the clear specifications!"
Daca astea sunt ceva gen "atoi converteste un string la un int" atunci pot scrie linistit:

Code: Select all

int atoi(const char *nptr);
{
   return 666;
}

"Cum gandesc? Gandesc pragmatic. Daca nici tu nu sti exact ce vrei, nu te astepta sa obtii de la mine exact ce vrei!"

[0ptr]

Pentru orice programator din lumea C/C++ atoi() are o insemnatate foarte clara: conversie ascii string la int. Sorry, daca nu am pastrat sintaxa.

[Ovidiu Cucu]

Pentru orice programator din lumea C/C++ atoi() are o insemnatate foarte clara: conversie ascii string la int.

Wrong!
Ia incearca, te rog, atoi() ca sa convertesti "0xFFFF" la int!

[Ovidiu Cucu]

Si o observatie suplimentara.
Nici una dintre functiile CRT standard nu face verificare pentru overflow/buffer overrun/NULL parameter.
Daca un intervievator se asteapta ca verificarile sa fie facute, fara sa specifice asta in mod explicit, atunci clar... e cu pluta pe Nicolina.

[Silviu Ardelean]

Pentru orice programator din lumea C/C++ atoi() are o insemnatate foarte clara: conversie ascii string la int.

Wrong!
Ia incearca, te rog, atoi() ca sa convertesti "0xFFFF" la int!

Intru si eu pe receptie... Dupa cum mentionai tu mai sus, atoi() e strtoul() cu baza 10. Deci, daca doresti sa te joci hexa, apeleaza la sursa (strtoul()) si foloseste-o corespunzator cu baza 16.

Daca un intervievator se asteapta ca verificarile sa fie facute, fara sa specifice asta in mod explicit, atunci clar...

Atat amar sa fie... unii au fantezi si se gandesc sa migreze atoi() la wide-char... ca doar atoi() nu vine de la ASCII si de _wtoi() nu s-a auzit.

[0ptr]

Pentru orice programator din lumea C/C++ atoi() are o insemnatate foarte clara: conversie ascii string la int.

Wrong!
Ia incearca, te rog, atoi() ca sa convertesti "0xFFFF" la int!

Intru si eu pe receptie... Dupa cum mentionai tu mai sus, atoi() e strtoul() cu baza 10. Deci, daca doresti sa te joci hexa, apeleaza la sursa (strtoul()) si foloseste-o corespunzator cu baza 16.

Silviu, mersi de completari.

Daca un intervievator se asteapta ca verificarile sa fie facute, fara sa specifice asta in mod explicit, atunci clar...

Atat amar sa fie... unii au fantezi si se gandesc sa migreze atoi() la wide-char... ca doar atoi() nu vine de la ASCII si de _wtoi() nu s-a auzit.

Mi se pare o cretinitate sa discuti de wchar_t cand e vorba de atoi() dar sunt convins ca exista specimene ce-si pun problema asta.

[Viorel]

Iată şi o variantă recursivă:

Code: Select all

static int work( int v, const char * p )
{
	unsigned char c = *p - '0';
	return c > 9 ? v : work(v * 10 + c, p + 1);
}

int my_atoi( const char * p )
{
	switch(*p)
	{
	case '+': return work(0, p + 1);
	case '-': return -work(0, p + 1);
	default:  return work(0, p);
	}
}