Ежедневный бит (е) C++ # 70, Общая проблема интервью C++: валидатор чисел
Сегодня мы рассмотрим распространенную проблему интервью C++: валидатор чисел.
Учитывая потенциальное число в виде строки, определите, содержит ли строка (только) допустимое десятичное число.
Формат числа (в этом порядке):
- десятичное число или целое число
- необязательно: буква "e" или "E" с последующим целым числом
целое число — это:
- необязательно: знак "+-"
- одна или несколько цифр (начальные нули допустимы)
десятичное число:
- необязательно: знак "+-"
- один из следующих форматов:
а) одна или несколько цифр, за которыми следует «.»
б) одна или несколько цифр, за которыми следует «.» с последующей одной или несколькими цифрами
c) «.» за которым следует одна или несколько цифр
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/KoKsnvveY.
Решение
Как это типично для задач такого типа, с алгоритмической точки зрения обсуждать нужно очень немногое, а только то, что мы должны стремиться обработать входные данные за один проход.
Основным испытанием для таких типов задач является декомпозиция проблемы и усердие. К счастью, спецификация проблемы завершена и намекает на потенциальную декомпозицию проблемы.
Одним из довольно простых способов обработки строки за один проход в C++ является использование итераторов, и мы можем начать с наиболее часто повторяющейся фразы в спецификации: «одна или несколько цифр».
// Greedily parse a number.
// Returns an iterator after the parsed portion
// (begin if parsing failed).
auto is_number(auto begin, auto end) {
if (begin == end) return begin;
auto it = begin;
// If leading zeroes were not OK, this is the only place
// we would have to modify.
while (it != end && std::isdigit(*it))
++it;
return it;
}
Мы пытаемся проанализировать число и вернуть итератор после проанализированной части. Это имеет два преимущества: мы можем легко обнаружить сбой на вызывающем сайте и легко продолжить синтаксический анализ.
Разбор целого числа — это просто вопрос добавления необязательного знака:
// Greedely parse an integer.
// Returns an iterator after the parsed portion (begin if parsing failed).
auto is_integer(auto begin, auto end) {
if (begin == end) return begin;
auto start = begin;
if (*start == '+' || *start == '-') ++start;
auto it = is_number(start, end);
return it == start ? begin : it;
}
Код для синтаксического анализа всего десятичного числа — самая сложная часть проблемы, поскольку у нас есть три потенциальных формата вокруг десятичного разделителя и необязательная экспоненциальная часть:
// Greedely parse an integer.
// Returns an iterator after the parsed portion (begin if parsing failed).
auto is_integer(auto begin, auto end) {
if (begin == end) return begin;
auto start = begin;
if (*start == '+' || *start == '-') ++start;
auto it = is_number(start, end);
return it == start ? begin : it;
}
// Greedily parse a decimal
// Returns an iterator after the parsed portion (begin if parsing failed).
auto is_decimal(auto begin, auto end) {
if (begin == end) return begin;
auto start = begin;
if (*start == '+' || *start == '-') ++start;
auto it = is_number(start,end);
// If we do not have leading digits before the '.'
// we must have both a '.' and digits after it.
bool required = (it == start);
if (it == end)
return required ? begin : it;
if (*it == '.') {
++it;
auto tail = is_number(it, end);
if (required && it == tail) return begin;
it = tail;
} else if (required) return begin;
if (it == end)
return end;
// Optional exponent:
if (*it == 'e' || *it == 'E') {
++it;
auto tail = is_integer(it, end);
if (tail == it) return begin;
return tail;
}
return it;
}
Наконец, чтобы вернуть логический ответ, нам нужно проверить, полностью ли мы проанализировали ввод:
bool is_valid_number(const std::string& s) {
// The is_decimal returns s.end()
// when the entire string parses as a number.
return is_decimal(s.begin(), s.end()) == s.end();
}
