Sunday, March 22, 2009

Algorithms: Convert Integer to string

Задача: перевести число в строку.

Возможно несколько вариантов рещения этой задачи.
Первый вариант - идем слева направо. Например, у нас есть число -123. Во-первых, мы во всех вариантах должны сначал проверить является ли число отрицательным, и перевести его в положительное (при этом запомнив, что изначально оно отрицательное). Далее, как мы можем получить число "1" из 123? Следующим образом:

123 / 100 = 1; 123 - 1 * 100 = 23 - первое число
23 / 10 = 2; 23 - 2 * 10 = 3 - второе число
3 / 1 = 3; 3 - 3 * 1 = 0 - третье число

Второй вариант предполагает проход числа справа налево. При этом как мы можем получить самое последнее число? Получив остаток от деления на 10: 123 / 10 = 3;

Алгоритм решения этой задачи приведен ниже:

If number less than zero
  Multiply number by -1
  Set negative flag
While number not equal to 0
  Add '0' to number % 10 and write this to temp buffer
  Integer divide number by 10
If negative flag is set
  Write '-' into next position in temp buffer
Write characters in temp buffer into output string in reverse order

И реализация на C#:

    1 /// <summary>

    2 /// Converts integer value to int string representation.

    3 /// </summary>

    4 /// <param name="value">Target integer value.</param>

    5 /// <returns>String representation of specified value.</returns>

    6 public static String Int32ToString(Int32 value)

    7 {

    8     char[] output = new char[10];

    9     bool isNegative = false;

   10     int i = 0;

   11 

   12     // First of all, check whether value is negative.

   13     if (value < 0)

   14     {

   15         isNegative = true;

   16         value *= -1;

   17     }

   18 

   19     do

   20     {

   21         // Find current number and shift to the corresponding char.

   22         output[i++] = (char)((value % 10) + '0');

   23 

   24         // Divide by 10, so on the next iteration we still

   25         // can obtain valid last number.

   26         value /= 10;

   27     }

   28     while (value > 0);

   29 

   30     // Add a minus sign "-" if isNegative flag is set.

   31     if (isNegative)

   32     {

   33         output[i] = '-';

   34     }

   35 

   36     // Construct the output string.

   37     string result = string.Empty;

   38     int position = output.Length - 1;

   39     while (position >= 0)

   40     {

   41         if (output[position] != '\0')

   42         {

   43             result += output[position];

   44         }

   45         position--;

   46     }

   47 

   48     return result;

   49 }

В следующий раз я раскажу как сделать обратное - из строки число.

Happy coding...

No comments :

Post a Comment