Реализация функции atoi()

Опубликовано Aug 29, 2011 в Массивы и строки | 12 коммент.

, ,

Напишите свою реализацию функции преобразования строки в число

int my_atoi(const char*  src)
{
  int result;
  // ваш код
  return result;
}

Цель данного задания: быстрая (до 20-ти минут) проверка базовых знаний С++ – циклы и работа со строками.
Время: до 20-ти минут
Формат выполнения: код пишется на листике, без доступа к документации

Если данная задача вам кажется слишком простой и не информативной для процедуры собеседования программиста С++, рекомендуем познакомиться с нашими критериями оценки.

Критерии оценки FulcrumWeb:

Прежде всего кандидат должен убедиться в полноте и однозначности постановки задачи.

В задаче сказано реализовать функцию преобразования, при этом название функции напоминает стандартную функцию С – atoi(). Если вам не знакома точная спецификация этой функции и принцип обработки ошибок – необходимо это уточнить.

Мы ожидаем услышать следующие вопросы:

  1. Что должна возвращать функция, если ее аргумент NULL  или вовсе не является числом.
  2. Каково должно быть поведение функции, если аргумент начинается с чисел, но заканчивается другими символами, например, “123hello”
  3. Какое значение или exception должна  возвращать функция, если ее значение больше диапазона, допустимого типом данных int
  4. Необходима ли поддержка разных платформ – 32 и 64 бита
  5. В какой системе исчисления должна работать эта функция? достаточно ли 10-тичной?
  6. Необходима ли поддержка отрицательных чисел? или результат “-1″ можно использовать для обозначения ошибки выполнения.
  7. нужно ли игнорировать whitespaces в начале строки, если да, то какие символы можно подразумевать под whitespaces (пробел, таб)?

После получения наших ответов мы ожидаем от вас реализации тела функции в течении 10-25 минут.

Оценка результатов:

Начинающему программисту (без опыта) мы простим полное отсутствие вопросов к постановке задачи, но, надеемся не встретить в реализации функции вызова математической функции возведения в степень pow().

От программистов с опытом работы мы ожидаем услышать хотя бы некоторые из перечисленных выше вопросов и безопасную реализацию, содержащую базовую обработку ошибок.


12 Коммент. : “Реализация функции atoi()”

  1. В самом простом варианте я бы дал такое решение:
    http://pastebin.com/N5EQRmAs

    int my_atoi(const char*  src)
    {
    	int result = 0;
    	int digit = 1;
    	const int DIGIT_DIFFERENCE = 10;
    	const char ZERO_SYMBOL = '0';
    	for(int i = (strlen(str)-1); i >= 0; i--)
    	{
    		result = result + (digit * int(str[i]-ZERO_SYMBOL));
    		digit = digit * DIGIT_DIFFERENCE;
    	}
    	return result;
    }

    Конечно, у него огромное количество минусов:
    1) Не работает с длинными числами
    2) Не работает с отрицательными числами
    3) Предполагается, что пользователь не совершает ошибок ввода и строка представляет собой исключительно последовательность цифр.

    • Галина says:

      Если поправить описку в названии параметра (src на str) – то это решение для собеседования вполне годится.
      Хороший способ получения числового значения из символьного.
      Хорошо, что нет явного возведения в степень.
      Совсем хорошо, если еще пункт 2) доделан – но это не трудно.
      Некорректный ввод и работа с длинными числами – это многовато для решения на листике за 20 мин.

  2. Вот намного более сложный вариант решения:
    http://pastebin.com/3xU2sdfq

     
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    static const char MINUS = '-';
    char* my_trimLeft(const char* src);
    int my_atoi(const char*  src);
    int main()
    {
    	cout << my_atoi("bjk vvh-)(-20856--fbhcfr f");
    	cin.get();
    	return 0;
    }
    // Implement the function, that transforms string into integer.
    int my_atoi(const char*  src)
    {
    	bool isNegative = false;
    	char* str = my_trimLeft(src);
    	if(str == NULL)
    	{
    		return EXIT_FAILURE;			// input error, terminating
    	}
    	if(str[0] == MINUS)
    	{
    		isNegative = true;
    		str++;
    	}
    	int result = 0;
    	int digit = 1;
    	const int DIGIT_DIFFERENCE = 10;
    	const char ZERO_SYMBOL = '0';
    	for(int i = (strlen(str)-1); i >= 0; i--)
    	{
    		result = result + (digit * int(str[i]-ZERO_SYMBOL));
    		digit = digit * DIGIT_DIFFERENCE;
    	}
    	if(isNegative == false)
    	{
    		delete [] str;
    		return result;
    	}
    	else
    	{
    		str--;
    		delete [] str;
    		return -result;
    	}
    }
    char* my_trimLeft(const char* src)
    {
    	if(strlen(src) == 0)	// there's no string
    	{
    		return NULL;
    	}
    	char* resultStr = new char[strlen(src)];
    	int srcIndex = 0;
    	int resultIndex = 0;
    	while(	(0 == isdigit(src[srcIndex]))
    		&&
    			(srcIndex < strlen(src))
    		)
    	{
    		if ((src[srcIndex] == MINUS) && (0 != isdigit(src[srcIndex+1])))
    		{
    			resultStr[resultIndex] = MINUS;
    			resultIndex++;
    		}
    		srcIndex++;
    	}
    	// now srcIndex indexes the first numeric in the string
    	while(	(0 != isdigit(src[srcIndex]))
    		&&
    			(srcIndex < strlen(src))
    		)
    	{
    		resultStr[resultIndex] = src[srcIndex];
    		resultIndex++;
    		srcIndex++;
    	}
    	resultStr[resultIndex] = '\0';
    	if(resultIndex == 0)	// no numerics in the string
    	{
    		return NULL;
    	}
    	return resultStr;
    }

    Единственный очевидный недостаток – не работает с длинными числами. С отрицательными числами работает. Ошибки обрабатывает. В случае смешанного ввода чисел и других символов обрабатывает первое вхождение числа в строку.

    • Галина says:

      Нормальное развитие решения. На собеседовании важно вписаться во временные рамки, поэтому нужно сначала прикинуть, насколько продвинутую функциональность удастся сделать за отведенное время.

      С этой точки зрения лучше 1-ый полностью работающий вариант, чем какие-то куски 2-ого. Разумеется, если удастся сделать вариант №2 по полной – это совсем замечательно.

  3. Олег says:

    Вот моя реализация, предусмотрено для максимального 10-значного значения, надеюсь вам придется по душе

    int myAtoi(char *string)
    {
    int result = 0;
    bool is_negative = false;
    int num[10];
    int s_lenght = strlen(string);
    int mn = 1;
    for(int i = s_lenght – 1; i >= 0; i–)
    {
    char chTemp = string[i];

    switch(chTemp)
    {
    case ’0′:
    num[i] = 0;
    break;
    case ’1′:
    num[i] = 1;
    break;
    case ’2′:
    num[i] = 2;
    break;
    case ’3′:
    num[i] = 3;
    break;
    case ’4′:
    num[i] = 4;
    break;
    case ’5′:
    num[i] = 5;
    break;
    case ’6′:
    num[i] = 6;
    break;
    case ’7′:
    num[i] = 7;
    break;
    case ’8′:
    num[i] = 8;
    break;
    case ’9′:
    num[i] = 9;
    break;
    case ‘-’:
    is_negative = true;
    break;
    }
    if(!is_negative)
    {
    result += num[i] * mn;
    mn *= 10;
    }
    }

    if(is_negative)
    result = -result;
    return result;
    }

    • Спасибо за код.
      Наши комментарии:
      - для преобразования символа в число достаточно от значения символа отнять значение нулевого символа – ’0′. Использование switch – громоздкое и более требовательное к ресурсам процессора.
      - is_negative в вашей реализации может менять свое значение несколько раз в одном числе – если встретится два знака ‘-’.
      - if(!is_negative) { result += num[i] * mn;} вы делаете только для положительных чисел. странная проверка. Минус в валидном числе будет последним знаком в ходе вашего цикла – но тогда зачем эта проверка?
      - и многое другое…

  4. Олег says:

    Спасибо за ответ. Код сырой, быстро хотел накатать)
    * Предполагается, что пользователь будет вводить корректные числа “123″, “-342″, а не “-23-4-2…”
    * про вычитание 0х30, эти коды уже рассматривались много где, как-то не хотелось пистаь про него, хотя так корректней
    * про if(!is_negative) { result += num[i] * mn;} , это потому, что массив num[i] не обнулён, хотел побыстрому сделать вот решил добавить этот if(!is_negative), ну а если обнулить массив, то условный оператор вполне можно убрать.
    Спасибо еще раз за внимание…

  5. int MyAtoi( const char* str )
    {
    	const int offset = '0';
    	const int sign = '-';
    	const int difference = 10;
     
    	int result = 0;
     
    	if( str != NULL )
    	{
    		int prev = 0;
    		int charsInString = strlen( str );
    		while( ( ( *str - offset ) < 0 || ( *str - offset ) > 9 ) && charsInString > 0 )
    		{
    			prev = *str;
    			charsInString--;
    			str++;
    		}
     
    		if( charsInString != 0 )
    		{
    			for( int i = 0, size = strlen( str ); i < size; ++i )
    			{
    				const int digit = str[i] - offset;
    				if( digit >= 0 && digit <= 9 )
    				{
    					int tmp = result;
     
    					result *= difference;
    					result += digit;
     
    					if( tmp > result )
    					{
    						result = tmp;
    						break; // overflow
    					}
    				}
    			}
     
    			if( prev == sign )
    			{
    				result = -result;
    			}
    		}
    		else
    		{
    			// error
    		}
    	}
    	else
    	{
    		// error
    	}
     
    	return result;
    }
  6. int MyAtoi(string str)
            {
                int result = 0, sign = 0;
                if (str[0] == '-') sign = 1;
                if (str != null && str.Length <= (10 + sign))
                {
                    for (int i = sign; i < str.Length; i++)
                    {
                        result = result * 10 + (str[i] - 48);
                    }
                    return ((sign == 0) ? result : -result);
                }
                return result;
            }
  7. Дмитрий says:

    Добрый день!
    Решил и я вставить свои пять копеек. Время выполнения 14 минут. Правда нет проверок и прочей обвязки так как нет ответов на 7 вопросов, описанных в начале поста :)

      result=0;
      bool sign=(*src=='-');
      (sign)? src++ :src;
      while(strlen(src)>0)
        result=result*10+ ((char)*(src++)-'0');
      result*= ((sign)?-1:1);
  8. Дмитрий says:

    Так будет оптимальнее;

    int my_atoi(const char*  src)
    {
      int result;
      const char*  tmp_src;
     
      tmp_src=src;
      result=0;
      if (*tmp_src=='-') tmp_src++;
      while(strlen(tmp_src)>0)
        result=result*10+ ((char)*(tmp_src++)-'0');
      result*= ((*src=='-')?-1:1);
      return result;
    }
  9. Дмитрий says:

    Даже так

    int my_atoi(const char*  src)
    {
      int result;
      const char*  tmp_src;
     
      tmp_src=src;
      result=0;
      if (*tmp_src=='-') tmp_src++;
      for(;strlen(tmp_src)>0; result=result*10+ ((char)*(tmp_src++)-'0'));
      result*= ((*src=='-')?-1:1);
      return result;
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*