Cum ati implementa functia atoi()?

Intrebari despre limbajul C++, standardul C++, STL, OOP in C++ sau alte subiecte nelegate de VisualC++
0ptr
Membru
Membru
Posts: 71
Joined: 01 Feb 2011, 23:27
Judet: Ilfov

Cum ati implementa functia atoi()?

Post by 0ptr » 19 Mar 2011, 01:26

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?



User avatar
cristianamarie
Membru++
Membru++
Posts: 480
Joined: 12 Mar 2009, 18:47
Judet: Iaşi
Location: Iasi

Re: Cum ati implementa functia atoi()?

Post by cristianamarie » 19 Mar 2011, 11:05

Nuclear launch detected

0ptr
Membru
Membru
Posts: 71
Joined: 01 Feb 2011, 23:27
Judet: Ilfov

Re: Cum ati implementa functia atoi()?

Post by 0ptr » 19 Mar 2011, 12:25

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:

User avatar
cristianamarie
Membru++
Membru++
Posts: 480
Joined: 12 Mar 2009, 18:47
Judet: Iaşi
Location: Iasi

Re: Cum ati implementa functia atoi()?

Post by cristianamarie » 19 Mar 2011, 15:34

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.
Nuclear launch detected

User avatar
Silviu Ardelean
Senior
Senior
Posts: 1175
Joined: 12 Jul 2007, 09:22
Judet: Timiş
Location: Timisoara
Contact:

Re: Cum ati implementa functia atoi()?

Post by Silviu Ardelean » 19 Mar 2011, 15:41

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;
}
Last edited by Silviu Ardelean on 21 Mar 2011, 18:52, edited 1 time in total.

patrujdoi
Junior
Junior
Posts: 6
Joined: 20 Mar 2011, 01:37

Re: Cum ati implementa functia atoi()?

Post by patrujdoi » 20 Mar 2011, 01:49

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
Membru
Membru
Posts: 71
Joined: 01 Feb 2011, 23:27
Judet: Ilfov

Re: Cum ati implementa functia atoi()?

Post by 0ptr » 20 Mar 2011, 11:19

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.

User avatar
Silviu Ardelean
Senior
Senior
Posts: 1175
Joined: 12 Jul 2007, 09:22
Judet: Timiş
Location: Timisoara
Contact:

Re: Cum ati implementa functia atoi()?

Post by Silviu Ardelean » 20 Mar 2011, 12:39

@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. ;)

User avatar
Ovidiu Cucu
Fondator
Fondator
Posts: 3776
Joined: 11 Jul 2007, 16:10
Judet: Iaşi
Location: Iasi
Contact:

Re: Cum ati implementa functia atoi()?

Post by Ovidiu Cucu » 20 Mar 2011, 16:54

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!"

0ptr
Membru
Membru
Posts: 71
Joined: 01 Feb 2011, 23:27
Judet: Ilfov

Re: Cum ati implementa functia atoi()?

Post by 0ptr » 20 Mar 2011, 17:12

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

User avatar
Ovidiu Cucu
Fondator
Fondator
Posts: 3776
Joined: 11 Jul 2007, 16:10
Judet: Iaşi
Location: Iasi
Contact:

Re: Cum ati implementa functia atoi()?

Post by Ovidiu Cucu » 20 Mar 2011, 17:19

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!

User avatar
Ovidiu Cucu
Fondator
Fondator
Posts: 3776
Joined: 11 Jul 2007, 16:10
Judet: Iaşi
Location: Iasi
Contact:

Re: Cum ati implementa functia atoi()?

Post by Ovidiu Cucu » 20 Mar 2011, 17:30

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

User avatar
Silviu Ardelean
Senior
Senior
Posts: 1175
Joined: 12 Jul 2007, 09:22
Judet: Timiş
Location: Timisoara
Contact:

Re: Cum ati implementa functia atoi()?

Post by Silviu Ardelean » 20 Mar 2011, 19:50

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.

0ptr
Membru
Membru
Posts: 71
Joined: 01 Feb 2011, 23:27
Judet: Ilfov

Re: Cum ati implementa functia atoi()?

Post by 0ptr » 21 Mar 2011, 11:35

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.

Viorel
Microsoft MVP
Microsoft MVP
Posts: 292
Joined: 13 Jul 2007, 12:26

Re: Cum ati implementa functia atoi()?

Post by Viorel » 21 Mar 2011, 12:21

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);
	}
}

Post Reply