Ну здравствуй, уважаемый читатель!

Кто же, как не мы, прожженные жизнью и монитором разработчики, знает как противоречив, труден и несправедлив этот мир технических собеседований! Пусть твои решения запускают космические корабли, или твой сервис удерживает миллионы запросов, опытный интервьюер всегда выведет тебя на чистую воду. Не можешь с ходу вспомнить разницу между сортировкой слиянием и вставками, не знаешь наизусть все SOLID принципы? О, друг мой, в отличие от тебя интервьюер подготовился серьёзнее и ещё с утра повторил эти важные темы. Твоя некомпетентность очевидна. Пересдача!

Конечно в следующий раз эти вопросы не застанут тебя врасплох, ты сам теперь поражаешься, как человек не может сходу реализовать сортировку кучей, или наизусть не помнит все правила балансировки красно-чёрных деревьев. Тебя снова зовут на собеседование, и какое удивительное совпадение: снова попадается тот же интервьюер. Вот он момент истины, теперь ты знаешь про сортировки всё, ты уже готов ударить по клавишам, как неожиданно читаешь постановку вопроса: “Реализовать парсер математических выражений”.

Неожиданно? Естественно. И поэтому, чтобы в этот раз всё получилось, предлагаю прямо здесь и сейчас разобраться с этим вопросом. Итак, приступим!

Постановка задачи: реализовать парсер математических выражений.

Конечно с такой формулировкой работать сложно, поэтому желательно на технических собеседованиях придерживаться правила: сначала обсудить ограничения, потом приступать к реализации. Если есть желание ввести интервьюера в состояние экстаза, то стоит предложить зафиксировать ограничения в виде набора тестов.

Введём следующий набор ограничений:

• Выражение не может содержать переменных или именованных констант, состоит только из чисел, арифметических знаков и скобок;
• Допустимы следующие арифметические знаки: +, -, *, /;
• Допустимы только круглые скобки;
• Если выражение содержит синтаксическую или вычислительную ошибку, то необходимо вместо результата вернуть сообщение об ошибке;

Сложность разбора или парсинга математических выражений заключается в том, что математические операции имеют разный приоритет, который также может изменяться с помощью скобок. Звучит сложно? На самом деле достаточно преобразовать выражение из инфиксной нотации в постфиксную с помощью алгоритма сортировочной станции, выполнить расчёт и всё! Казалось бы, можно на этом завершать пост, но вероятнее всего злобный интервьюер захочет углубиться в детали, а ещё, чего доброго, потребует реализации. Поэтому продолжим.

Инфиксная нотация - форма записи математических выражений, в которой операторы (в нашем случае арифметические знаки) записаны между операндами (в нашем случае числами), на которые они применяются. Порядок вычислений определяется приоритетом операторов, но может регулироваться скобками. Таким образом, инфиксная нотация - это стандартная форма записи выражений, которой нас обучали ещё в школе, например: 1 + (2 - 3) * 4.

Постфиксная нотация - форма записи математических выражений, в которой операторы записаны после операндов, на которых они применяются. В данной нотации отсутствует приоритет операций, а следовательно отсутствуют скобки. Например, выражению выше будет соответствовать следующее выражение в постфиксной нотации: 2 3 - 4 * 1 + или 4 2 3 - * 1 +.

Полную реализацию на C# можно найти на GitHub проекта coding-interview, а пока разберём алгоритм вычисления выражения, записанного в постфиксной нотации. Создадим класс, который на вход будет принимать последовательное множество токенов (операторов и операндов), а на выходе будет возвращать результат в ввиде вычисленного операнда.

Если токен является операндом, то добавляем операнд в стек операндов.

Если же токен является оператором, то достаём необходимое количество операндов из стека, производим вычисление и добавляем результат вычисления назад в стек операндов. Если же в стеке нет необходимого числа элементов для вычисления оператора, то сигнализируем об ошибке.

Осталось лишь добавить реализацию возвращения результата - единственного элемента в стеке. Если после обработки всех токенов в стеке находится больше одного элемента, то это будет сигнализировать о наличии несоответствия между операторами и операндам. Если же в стеке нет элементов, то это значит, что на вход была подана пустая последовательность.

На этом мне надо прощаться, а уже в следующем посте разберём реализацию алгоритма сортировочной станции.