Всё, что вам не рассказали про Shunting Yard

info@vsetut.pro

Стать автором

Вернуться

09.05.2025 13:24:27 | Хабр

Хабы: Алгоритмы, Компиляторы, Программирование, Системное программирование

Алгоритм сортировочной станции (Shunting Yard) был предложен Дейкстрой ещё в 1961 году и служит для преобразования математических выражений из привычной всем инфиксной записи (где операторы стоят между операндами, как в 1 + 2 * 3) в постфиксную (обратную польскую нотацию, 1 2 3 * +), удобную для дальнейшего вычисления. Однако есть один важный момент, который почти всегда упускается или замалчивается: алгоритм предполагает, что входное выражение уже синтаксически корректно.

Ни в Википедии, ни в большинстве обучающих статей вы не встретите слов о том, что выражения вроде + (1 2, 3 * 4 + ) или sin(+) должны вызывать ошибку. В лучшем случае они просто не вычисляются (что будет понятно лишь на этапе обработки в обратной польской записи), в худшем – дают бессмысленный результат. Алгоритм продолжает работать, даже если выражение изначально некорректно – и мало кто задумывается, почему это плохо.

Эта статья – попытка исправить эту несправедливую ситуацию, в которой мы не только реализуем алгоритм сортировочной станции «на максималках» с поддержкой констант, переменных, функций, унарных операторов, приоритетов и ассоциативности, но и добавим полноценную проверку корректности выражения по ходу разбора.

Подробнее