Наука постоянно развивается, технологии стремительно врываются в нашу жизнь, появляются новые инструменты и возможности, неизменно лишь одно - угрюмое выражение лица твоего интервьюера. И если с чтением эмоций интервьювера мы разобрались, то с чтением выражения у нас всё ещё есть проблемы. Поэтому в данном посте разберём самую простую тему в контексте данной задачи - разбиение исходной строки на отдельные токены.
Как упоминалось в предыдущих постах про постфиксную нотацию и алгоритм сортировочной станции, мы имеем следующие виды токенов:
- Знаки арифметических операций
+, -, *, /; - Круглые скобки
(, ); - Вещественные числа. Для простоты ограничимся только числами с десятичным разделителем;
- В качестве разделителей токенов может выступать только символ пробела.
Создадим тело основного метода на C#. Будем читать выражение символ за символом и сразу обрабатывать. Для нашего случая этого достаточно, в других случаях лексические анализаторы могут требовать более сложных подходов. Данная тема достаточно хорошо рассмотрена в той самой книге.
Для начала реализуем самый простой вариант: входная строка содержит только одно число, пробелы и операторы отсутствуют.
- Пока есть символы, добавляем символы в отдельное хранилище, на основе которых будем формировать результирующее число;
- Если в хранилище есть символы, то конвертируем символы в число и добавляем в список результирующих токенов.
Усложним немного задачу: разрешим использование нескольких чисел, разделенных пробелами. Тогда разбиение на токены можно представить в следующем виде:
Пока есть символы, анализируем очередной символ:
Если символ является разделителем (пробелом), то конвертируем сохраненные в хранилище символы в число и добавляем в список результирующих токенов;
Иначе используем символ для формирования числа в отдельном хранилище;
Если в хранилище остались символы, то конвертируем символы в число и добавляем в список результирующих токенов.
Добавим теперь поддержку обработки операторов. Так как в нашей постановки задачи все операторы выражаются ровно одним символом, то при встрече символа оператора будем сразу добавлять оператор в результирующую последовательность. При этом если в хранилище содержатся символы для формирования числа, то конвертируем их в число. Тогда финальный алгоритм будет выглядеть следующим образом:
- Пока есть символы, анализируем очередной символ:
- Если символ является разделителем (пробелом), то конвертируем сохраненные в хранилище символы в число и добавляем в список результирующих токенов;
- Если символ является оператором, то конвертируем сохраненные в хранилище символы в число и добавляем в список результирующих токенов, после чело добавляем токен оператора в результирующий список;
- Иначе используем символ для формирования числа в отдельном хранилище;
- Если в хранилище остались символы, то конвертируем символы в число и добавляем в список результирующих токенов.
Как всегда полную реализацию можно посмотреть на GitHub проекта coding-interview, а этим постом будем заканчивать тему разбора математических выражений. Надеюсь, что всё было познавательно и интересно. До встречи!