Правила преобразования строки в число

Преобразование строки в число – базовая операция в информатике, лежащая в основе чтения данных, вычислительной математики, анализа форматов, задач на системы счисления и моделирования. Тема сочетает формальные аспекты (грамматики допустимых представлений чисел), алгоритмические (конечные автоматы и линейные преобразователи), инженерные (устойчивость к ошибкам формата, переполнению, локальным соглашениям) и экзаменационные (трассировка/валидация ввода, перевод между основаниями, работа со строками/файлами). Ниже последовательно изложены термины, строгие правила преобразования, корректные алгоритмы для целых и вещественных чисел (в том числе с основанием p), анализ сложности и типичных ошибок. Завершает материал практикум из 5 упражнений формата ЕГЭ.

Понятийный аппарат и постановка задачи

Строка – конечная последовательность символов алфавита.
Числовая строка – строка, удовлетворяющая грамматике выбранного числового формата (целое/вещественное, основание p, научная нотация).
Парсинг (разбор) – проверка соответствия формату и вычисление численного значения.
Допустимые символы зависят от формата: цифры, знак (‘+’/‘−’), разделитель дробной части, индикатор порядка (‘e’/‘E’), префиксы основания (опционально), пробелы (обычно только по краям).
Цель: по входной строке s вычислить число N (или выдать ошибку формата), гарантируя: (а) детерминизм; (б) линейную сложность O(∣s∣); (в) корректность по спецификации.

Формальные правила (грамматики)

Ниже – академическая (упрощённая и учебно-стандартная) грамматика. Символы в кавычках – литералы, digit10 – десятичная цифра, digit_p – цифра в основании p (см. ниже).

1. Целое (десятичное)
   

   int10        := sign? digits10

   sign         := «+» | «-«

   digits10     := digit10 (digit10)*

   digit10      := «0» | «1» | ... | «9»

   Правила:

   • Внутренние пробелы запрещены; ведущие/замыкающие допускаются и удаляются при предобработке (trim).

   • Пустая строка и строка «+»/«−» без цифр – ошибка.

   • Ведущие нули допустимы (семантика не меняется).

2. Целое в основании p, 2≤p≤36 
   

   int_p        := sign? digits_p

   digits_p     := digit_p (digit_p)*

   digit_p      := "0".."9","A".."Z" (регистр-нечувствительно)

   value(c)     := 0..35, где A/a→10, B/b→11, ...

   условие      := value(c) < p

   Правила:

   Любой символ с value(c) ≥ p → ошибка.

   Регистр букв не важен, смешение допустимо.

   Префиксы вида 0x, 0b в учебной модели считаются частью строки; разрешать их – только если оговорено (см. «Специфика реализации»).

3. Десятичное вещественное (без экспоненты)
   

   go

   float10      := sign? ((digits10 «.» digits10?) | («.» digits10) | digits10 «.»)

   Правила:

   Должна присутствовать хотя бы одна десятичная цифра.

   Разделитель дробной части – «.» (универсальная учебная договорённость). Локальная «,» используется только после явного преобразования.

4. Научная нотация (экспоненциальная форма)
   

   sci10        := (int10 | float10) ((«e»|»E») exp)?

   exp          := sign? digits10

   значение     := mantissa × 10^(exp)

   Правила:

   • После e/E – обязательно непустые десятичные цифры, опциональный знак.

   • Пробелы вокруг e/E запрещены.

Алгоритмы разбора (валидация + вычисление)

1. Конечный автомат (универсальный каркас)
   

   Состояния: START → SIGN? → INT → (DOT → FRAC)? → (E → ESIGN? → EXP)? → END.
   На каждом переходе проверяются допустимые символы и накапливаются компоненты (знак, целая часть, дробная часть, показатель). Любая ошибка (неожиданный символ, пустой компонент там, где обязателен) немедленно прерывает разбор.

   Сложность: один левоправый проход → O(n) по времени и O(1) по памяти (без вспомогательных структур).

2. Целое в основании p
   

   Итерационный накопитель:

   
   

   для каждой цифры слева направо; знак применяется в конце.
   Проверка переполнения (для фиксированной разрядной сетки, если требуется): до умножения проверять, что acc ≤ (MAX - digit)/p.

3. Вещественное (десятичное)
   

   Вариант A (рациональная форма):

   • Целая часть: как у целого в основании 10.

   • Дробная часть 
     

   • Результат 

   Вариант B (инкрементальная):
   

   • Для каждой дробной цифры 

   • Уязвимо к накоплению погрешности (IEEE-754); учебно предпочтителен вариант А

4. Научная нотация
   

   Сначала вычислить мантиссу, затем скорректировать порядок:

   

   При необходимости – масштабировать целочисленно (для рационального представления) либо делегировать умножение типу с плавающей точкой/десятичной арифметике.

Корректность, инварианты и сложность

Инварианты разбора:

• На вход каждого состояния автомата префикс строки валиден по грамматике.

• Аккумулятор acc всегда содержит точное значение префикса (в выбранной арифметике).

• Для оснований p всегда соблюдается value(c) < p.

Сложность:

• Время: линейное O(n).

• Память: O(1) (без хранения всего числа, кроме счётчиков и аккумуляторов).

• Точность: для целых – точная; для вещественных – точная в рациональной форме, приближённая в бинарном IEEE-754 (оговаривается в спецификации).

Специфика реализации и учебные соглашения

1. Разделители и пробелы
   

   • Trim: удалять только ведущие/замыкающие пробелы (U+0020); внутренние пробелы не допускаются.

   • Разделители тысяч (пробелы, неразрывные пробелы, точки, запятые) запрещены в учебной модели. Если вход содержит их, требуется явная очистка.

2. Регистр и буквы-«цифры»
   

   Для оснований >10 допускаются A..Z/a..z; значение определяется регистронезависимо: A/a→10, …, Z/z→35.

3. Локаль: «.» против «,»
   

   В ЕГЭ рекомендуется унифицировать вещественный ввод под «.» и, при необходимости, выполнять предобработку:

   s = s.replace(',', '.')

   Только если по условию явно сказано, что десятичный разделитель – запятая.

4. Специальные литералы
   

   NaN, Inf, Infinity, префиксы 0x/0b/0o – вне учебной модели, если не оговорено. На ЕГЭ – не использовать, если форматом не предусмотрено.

5. Обработка ошибок
   

   • Пустая строка, одиночный знак, «.» без цифр, e без показателя, лишние символы – ошибка формата.

   • Цифра вне диапазона основания p – ошибка.

   • Переполнение фиксированного диапазона – ошибка или насыщение (по спецификации).

Типичные ошибки и анти-паттерны

1. Игнорирование знака в середине (например, 12-3) – недопустимо.

2. Двойной десятичный разделитель: 12.3.4 – ошибка.

3. Экспонента без цифр: 1e, 1e+ – ошибка.

4. Локальная запятая без предобработки → неверный парсинг.

5. Смешение оснований: цифра F при p=10 – ошибка.

6. Тихое переполнение: отсутствие проверки границ типа при большой длине.

7. Неполное trim: невидимые whitespace (например, \t, \r) не удаляются – лучше нормализовать все пробельные.

Связь с подготовкой к ЕГЭ по информатике

• Строки → числа при чтении файлов: map(int, ...), подсчёт/фильтрация чисел, поиск максимумов/сумм.

• Системы счисления: вычисление значения слова в основании ppp; перевод между основаниями; проверка корректности записи.

• Научная нотация: трассировка программ, где числа генерируются/нормализуются экспонентой.

• Алгоритмика строк: построение конечного автомата для валидации ввода (задачи на подсчёт корректных строк, регулярные шаблоны).

• Анализ ошибок формата: «сколько строк файла будут успешно преобразованы?» – типичный вопрос на внимательность к правилам.

Практикуя собственные парсеры (целые в p, вещественные с «.» и экспонентой), выпускник укрепляет навыки работы со строками, системами счисления и контролем ошибок – это прямые компетенции ЕГЭ.

Псевдокод (учебные эталоны)

1. Целое в основании p (валидация + значение)
   

   function from_base_p(s, p):

     s := trim(s)

     if s == "" then error

     sign := +1

     if s[0] == '+' then s := s[1..]

     else if s[0] == '-' then sign := -1; s := s[1..]

     if s == "" then error

     acc := 0

     for c in s:

       v := value(c)  // '0'..'9','A'..'Z' → 0..35

       if v < 0 or v >= p then error

       acc := acc * p + v

     return sign * acc

2. Десятичное вещественное с опциональной экспонентой
   

   function parse_float10(s):

     s := trim(s).replace(',', '.')  // по оговорке

     if s == "" then error

     read optional sign

     read digits before dot into I (может быть пусто)

     if next == '.' then read digits after dot into F (может быть пусто)

     else F := ""  // нет дробной части

     if I == "" and F == "" then error

     read optional ('e'|'E'), then optional sign, then EXP digits (непусто) 

     if 'e'/'E' встречено и EXP пусто → error

     int_val := value(I)    // как в целых

     frac_val := value(F) / 10^{len(F)}

     mantissa := (int_val + frac_val) * sign

     if экспоненты нет: return mantissa

     else return mantissa * 10^{exp_value}

Оценка корректности и проверяемость

• Доказательство по префиксу: любой префикс, допущенный автоматом, расширяем только допустимыми символами.

• Тест-наборы:
  

  • Позитивные: "0", "-0", "007", "+12.34", ".5", "5.", "1e-3", "A1" при p=16p=16p=16.

  • Негативные: "", "+", "-", ".", "1e", "1e+", "12 34", "1,2" без предобработки, "G" при p=16p=16p=16, "2" при p=2p=2p=2.

Практикум: 5 упражнений (ЕГЭ-ориентированный формат)

Упражнение 1. «Система счисления: валидность и значение»
Условие. Дана строка S = «1A0F» и основание p = 16.

1. Проверьте корректность записи по правилам.

2. Вычислите десятичное значение.
   Критерии. Верный мэппинг A→10, F→15; применение схемы acc:=acc⋅p+digit.
   Подсказки. Поразрядно: 1⋅16³+10⋅16²+0⋅16+15.

Упражнение 2. «Вещественные строки: грамматика и ошибки»
Условие. Для каждой строки определить, является ли она корректным десятичным вещественным числом в учебной модели и почему:
«12.0», «.75», «5.», «1e-3», «1e+», « -0.25 », «3,14».
Критерии. Умение применить грамматики.
Подсказки. 1e+ – ошибка (нет цифр показателя); «3,14» – корректно только после явного replace(',', '.').

Упражнение 3. «Автомат для десятичного числа»
Условие. Постройте конечный автомат (состояния и переходы) для разбора sci10, включив переходы для: знака, целой/дробной части, точки, e/E, знака экспоненты и цифр экспоненты, а также завершающее состояние.
Критерии. Полное покрытие вариантов digits, digits. , .digits, digits.digits, опциональной экспоненты.
Подсказки. Минимально нужны состояния: START, SIGN, INT, DOT, FRAC, E, ESIGN, EXP, END.

Упражнение 4. «Сколько строк корректно?»
Условие. В файле каждая строка – кандидат на целое в основании p=7. Строки:
«1206», «205», «51A», «-060», « +34 », «7».
Подсчитайте, сколько строк пройдут валидацию и будут корректно преобразованы, и объясните отказ для остальных.
Критерии. Проверка value(c) < 7, учёт trim, единственного знака и отсутствия пустой части.
Подсказки. Символы A и 7 недопустимы при p=7.

Упражнение 5. «Экспоненциальная нормализация»
Условие. Дан корректный sci10: «−3.125e+4».

1. Представьте число без экспоненты (в виде десятичной дроби).

2. Выполните обратную операцию нормализации к виду m × 10^k с 1≤∣m∣<10.
   Критерии. Правильный сдвиг десятичной точки на k позиций; понимание мантиссы и порядка.
   Подсказки. −3.125e+4 = −31250; нормализованная форма: −3.125 × 10^4.

Заключение

Преобразование строки в число – дисциплина чётких правил: формальная грамматика, конечный автомат, линейный накопитель, явные соглашения о локали и системе счисления, проверка границ и ошибок формата. Такой подход делает решения детерминированными, тестируемыми и эффективными. Для ЕГЭ это критично: от корректного парсинга зависят задачи на системы счисления, анализ файлов/строк и вычисление значений выражений. Освоив предложенные правила и алгоритмы, а также отработав упражнения, выпускник получает устойчивые навыки, напрямую повышающие результат в заданиях повышенной и высокой сложности.