Page 1 of 2

Cum ati implementa functia atoi()?

Posted: 19 Mar 2011, 01:26
by 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?

Re: Cum ati implementa functia atoi()?

Posted: 19 Mar 2011, 11:05
by cristianamarie

Re: Cum ati implementa functia atoi()?

Posted: 19 Mar 2011, 12:25
by 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! :thumbup:

Re: Cum ati implementa functia atoi()?

Posted: 19 Mar 2011, 15:34
by 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.

Re: Cum ati implementa functia atoi()?

Posted: 19 Mar 2011, 15:41
by 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;
}

Re: Cum ati implementa functia atoi()?

Posted: 20 Mar 2011, 01:49
by 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;
}

Re: Cum ati implementa functia atoi()?

Posted: 20 Mar 2011, 11:19
by 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.

Re: Cum ati implementa functia atoi()?

Posted: 20 Mar 2011, 12:39
by 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. ;)

Re: Cum ati implementa functia atoi()?

Posted: 20 Mar 2011, 16:54
by Ovidiu Cucu
0ptr wrote:...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! :thumbup:
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!"

Re: Cum ati implementa functia atoi()?

Posted: 20 Mar 2011, 17:12
by 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. :)

Re: Cum ati implementa functia atoi()?

Posted: 20 Mar 2011, 17:19
by Ovidiu Cucu
0ptr wrote: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!

Re: Cum ati implementa functia atoi()?

Posted: 20 Mar 2011, 17:30
by 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. :)

Re: Cum ati implementa functia atoi()?

Posted: 20 Mar 2011, 19:50
by Silviu Ardelean
Ovidiu Cucu wrote:
0ptr wrote: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. :)
Ovidiu Cucu wrote: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.

Re: Cum ati implementa functia atoi()?

Posted: 21 Mar 2011, 11:35
by 0ptr
Silviu Ardelean wrote:
Ovidiu Cucu wrote:
0ptr wrote: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.
Silviu Ardelean wrote:
Ovidiu Cucu wrote: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.

Re: Cum ati implementa functia atoi()?

Posted: 21 Mar 2011, 12:21
by 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);
	}
}