Sunday, March 22, 2009

Algorithms: Convert string to integer

Задача: необходимо преобразовать строку в число.

Для начала предположим, что строка у нас находится в кодировке ASCII. Наиболее очевидным и простым решением является проход строки справа налево.

Давайте на примере рассмотрим решение задачи. Итак, у нас есть строка "437". Двигаясь слева направо, мы на первом шаге берем символ "4". Как мы можем перевести "4" в соответствующее число: 4? Так как у нас строка в ASCII кодировке, мы можем взять '4' - у которого числовое представление 52 и вычесть 48, т.е. числовое представление '0'.

Примечание: более подробную информацию по кодировке ASCII можно найти здесь: American Standard Code for Information Interchange (ASCII).

Далее, получив второй символ "3" нам необходимо умножить предыдущее число 4 на 10 и найти числовое представление символа "3". После этого результат складываем и запоминаем: 4 * 10 + 3. На следующем шаге получим (4 * 10 + 3) * 10 + 7.

Этот алгорим можно представить как:

Start number at 0
If the first character is '-'
    Set the negative flag
    Start scanning with the next character
For each character in the string
    Multiply number by 10
    Add (digit character - '0') to number
Return number

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

    1 /// <summary>

    2 /// Converts string to integer.

    3 /// </summary>

    4 /// <param name="input">Input string.</param>

    5 /// <returns>Resulting integer value.</returns>

    6 public static Int32 StringToInt32(String input)

    7 {

    8     // Validate input parameter.

    9     if (String.IsNullOrEmpty(input))

   10     {

   11         throw new ArgumentNullException("input");

   12     }

   13 

   14     Int32 position = 0;

   15     Boolean isNegative = false;

   16     Int32 result = 0;

   17 

   18     if (input.Length == 1 && !char.IsDigit(input[position]))

   19     {

   20         throw new InvalidOperationException();

   21     }

   22 

   23     // Validate whether input string starts with "-".

   24     if (input[position] == '-')

   25     {

   26         isNegative = true;

   27         position = 1;

   28     }

   29 

   30     while (position < input.Length)

   31     {

   32         if (!char.IsDigit(input[position]))

   33         {

   34             throw new InvalidOperationException();

   35         }

   36 

   37         result *= 10;

   38         result += (input[position] - '0');

   39 

   40         position++;

   41     }

   42 

   43     if (isNegative)

   44     {

   45         result *= -1;

   46     }

   47 

   48     return result;

   49 }

Сложность такого алгоримта - O(n).

PS: В следующий раз я покажу как перевести число из римской системы счисления в арабскую: XXI -> 21.

Happy coding...

No comments :

Post a Comment