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

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

Алгоритм широко известен, а его описание можно найти даже на Википедии. Однако есть один важный момент, который почти всегда упускается или замалчивается: алгоритм предполагает, что входное выражение уже синтаксически корректно.

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

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

Почему вообще используется сортировочная станция?

Разбор произвольных математических выражений – задача не такая уж и простая. Чтобы вычислить выражение, записанное в привычной инфиксной форме (1 + 3) * 2^2^3, нужно учитывать приоритеты операций, скобки и ассоциативность операторов. Использовать для этого можно самые разные подходы.

Один из самых надёжных и элегантных – рекурсивный нисходящий парсинг. Он основан на формальной грамматике выражений и позволяет чётко структурировать код, а также удобно обрабатывать ошибки. Такой парсер может сразу строить постфиксную форму (Reverse Polish Notation), синтаксическое дерево или даже генерировать байткод, в зависимости от задачи.

Тем не менее, алгоритм сортировочной станции остаётся популярным благодаря своей академической простоте и универсальности в условиях ограниченных ресурсов. Он особенно удобен в ситуациях, где нет необходимости строить полноценное дерево разбора, – например, в простых калькуляторах, микроконтроллерах, интерпретаторах выражений или при генерации промежуточных представлений для последующего перевода в другой вид (например, в LaTex). Алгоритм является итеративным, требует минимум памяти и обеспечивает стабильную работу при фиксированных правилах приоритетов и ассоциативности.

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

Классический алгоритм

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

(1 + 3) * 2^2^3

Правильный порядок вычислений здесь задаётся приоритетами операций, ассоциативностью и скобками: сначала нужно посчитать выражение в скобках, затем возведения в степень, причём справа налево и лишь затем выполнить умножение. Алгоритм сортировочной станции позволяет преобразовать такое выражение в постфиксную запись (Reverse Polish Notation), в которой порядок выполнения задан явно:

1 3 + 2 2 3 ^ ^ *

Чтобы получить такую запись, при чтении токенов слева направо используется два хранилища: стек операторов и выходной список для rpn.

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

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

• Скобки позволяют временно "переключать" приоритеты: открывающая скобка помещается в стек и отсекает всё, что было до неё, а при встрече закрывающей скобки стек разгружается до соответствующей открывающей и выталкивает функцию, если та оказалась перед открывающей скобкой.

Для формальности давайте посмотрим на псевдокод канонического алгоритма сортировочной станции:

operators = {
    "+": {precedence: 1, associative: "left"},
    "-": {precedence: 1, associative: "left"},
    "*": {precedence: 2, associative: "left"},
    "/": {precedence: 2, associative: "left"},
    "^": {precedence: 3, associative: "right"}
}

stack = []
rpn = []

for token in tokens:
    if token is a constant, number or variable:
        rpn.push(token) // операнды сразу помещаются в выходной список

    else if token is a function:
        stack.push(token)

    else if token is a delimeter:
        // выталкиваем всё до открывающей скобки
        while (stack.top() is not "("):
            rpn.push(stack.pop())

        assert stack is not empty // если стек пуст, в выражении пропущена открывающая скобка

    else if token is an operator:
        while (stack.top() is operator and (stack.top() has greater precedence than token or (stack.top() and token have the same precedence and token is left-associative)):
            rpn.push(stack.pop())

        stack.push(token)

    else if token is "(":
        stack.push(token)

    else if token is ")":
        // выталкиваем всё до открывающей скобки
        while (stack.top() is not "("):
            rpn.push(stack.pop())

        assert stack is not empty // если стек пуст, в выражении пропущена открывающая скобка
        stack.pop()

        if stack.top() is a function:
            rpn.push(stack.pop())

// выталкиваем все оставшиеся в стеке токены (если встретится "(", то в выражении пропущена закрывающая скобка)
while (stack is not empty):
    assert stack.top() is not "("
    rpn.push(stack.pop())

Алгоритм действительно работает быстро и элегантно, но в своей классической форме он исходит из предположения, что входное выражение уже корректно. Это допущение не всегда справедливо – и если в выражении окажется ошибка, пользователь, скорее всего, получит либо загадочный результат, либо вовсе ничего. Англоязычная Википедия, по крайней мере, честно предупреждает: алгоритм в базовом виде способен обработать даже большинство некорректных выражений, за исключением, пожалуй, выражений с несогласованными скобками. Русскоязычная версия молчит и об этом – впрочем, от неё, пожалуй, никто и не ждёт полной технической достоверности.

Поддержка унарного минуса

Классический алгоритм shunting yard не различает унарные и бинарные операторы: он предполагает, что тип каждого оператора известен заранее и не зависит от контекста. Это подходит для большинства операторов, но в случае унарного минуса такой подход не работает: один и тот же символ - может означать как бинарную операцию вычитания (a - b), так и унарную операцию смены знака (-a).

Чтобы корректно обрабатывать унарный минус, необходимо:

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

• Представлять унарный минус отдельным токеном – например, ~, отличающимся от обычного - по имени и приоритету.

• Добавить унарный минус в таблицу приоритетов и ассоциативностей: он должен иметь более высокий приоритет, чем бинарные операторы (но не выше операции возведения в степень), и быть правоассоциативным.

Модификация алгоритма

В алгоритме достаточно будет лишь завести токен prev = null, отслеживающий последний обработанный токен выражения. При обработке оператора - в случае успешной проверки на унарность, нужно будет заменить его на ~ и поместить в стек:

operators = {
    ...
    "~": {precedence: 3, associative: "right"}
}

prev = null // последний обработанный токен

for token in tokens:
    ...

    else if token is "-" and prev is null, operator, delimeter or "(":
        stack.push("~") // меняем токен на унарный и кладём его в стек
    ...

    prev = token

Теперь алгоритм способен корректно переводить выражения с унарным минусом:

Входное выражение	Результат разбора
-1	1 ~
-(1+2)	1 2 + ~
-----5	5 ~ ~ ~ ~ ~
-max(-4, -5)	4 ~ 5 ~ max ~
-4^-2^-3	4 2 3 ~ ^ ~ ^ ~

Пример разбора выражения

Давайте посмотрим, как shunting yard обрабатывает вот такое выражение:

2 * 9 / 2.5 + cos(pi) * max(3^2 * (7 - 1), x)

токен	действие	стек	rpn
2	кладём 2 в rpn	[]	[2]
*	кладём * в стек	[*]	[2]
9	кладём 9 в rpn	[*]	[2 9]
/	перекладываем * из стека в rpn	[]	[2 9 *]
	кладём / в стек	[/]	[2 9 *]
2.5	кладём 2.5 в rpn	[/]	[2 9 * 2.5]
+	перекладываем / из стека в rpn	[]	[2 9 * 2.5 /]
	кладём + в стек	[+]	[2 9 * 2.5 /]
cos	кладём cos в стек	[+ cos]	[2 9 * 2.5 /]
(	кладём ( в стек	[+ cos (]	[2 9 * 2.5 /]
pi	кладём pi в rpn	[+ cos (]	[2 9 * 2.5 / pi]
)	выкидываем ( из стека	[+ cos]	[2 9 * 2.5 / pi]
	перекладываем cos из стека в rpn	[+]	[2 9 * 2.5 / pi cos]
*	кладём * в стек	[+ *]	[2 9 * 2.5 / pi cos]
max	кладём max в стек	[+ * max]	[2 9 * 2.5 / pi cos]
(	кладём ( в стек	[+ * max (]	[2 9 * 2.5 / pi cos]
3	кладём 3 в rpn	[+ * max (]	[2 9 * 2.5 / pi cos 3]
^	кладём ^ в стек	[+ * max ( ^]	[2 9 * 2.5 / pi cos 3]
2	кладём 2 в rpn	[+ * max ( ^]	[2 9 * 2.5 / pi cos 3 2]
*	перекладываем ^ из стека в rpn	[+ * max (]	[2 9 * 2.5 / pi cos 3 2 ^]
	кладём * в стек	[+ * max ( *]	[2 9 * 2.5 / pi cos 3 2 ^]
(	кладём ( в стек	[+ * max ( * (]	[2 9 * 2.5 / pi cos 3 2 ^]
7	кладём 7 в rpn	[+ * max ( * (]	[2 9 * 2.5 / pi cos 3 2 ^ 7]
-	кладём - в стек	[+ * max ( * ( -]	[2 9 * 2.5 / pi cos 3 2 ^ 7]
1	кладём 1 в rpn	[+ * max ( * ( -]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1]
)	перекладываем - из стека в rpn	[+ * max ( * (]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1 -]
	выкидываем ( из стека	[+ * max ( *]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1 -]
,	перекладываем * из стека в rpn	[+ * max (]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1 - *]
x	кладём x в rpn	[+ * max (]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1 - * x]
)	выкидываем ( из стека	[+ * max]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1 - * x]
	перекладываем max из стека в rpn	[+ *]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1 - * x max]
	перекладываем * из стека в rpn	[+]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1 - * x max *]
	перекладываем + из стека в rpn	[]	[2 9 * 2.5 / pi cos 3 2 ^ 7 1 - * x max * +]

Проверка корректности выражений на лету

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

Одни из самых частых видов ошибок – нарушение порядка следования токенов и некорректная запись вызова функции. Например:

• * 2 + 3 – выражение начинается с оператора.

• 4 * + 3 – подряд идут два оператора.

• 3 4 + – два операнда подряд без оператора.

• sin 5 – пропущены скобки после функции.

• max (, 5) – разделитель функции идёт сразу после открывающей скобки.

Выражения, в которых открывающая скобка не закрыта ((1 + 2) или закрывающая скобка появляется слишком рано (2 + 3)) успешно отловятся уже текущей версией алгоритма.

Чтобы обнаруживать такие ошибки, достаточно ввести переменную expect с ожидаемым типом токена – операнд, оператор или открывающая скобка (для обработки вызова фукции). В начале выражения ожидается операнд, после него – оператор, и так далее. Скобки корректируют ожидания: открывающая скобка допускается на месте операнда, а закрывающая – только там, где ожидается оператор (т.е. после операнда или закрытия вложенного выражения). При этом после функции обязательно должна идти открывающая скобка.

Модифицируем алгоритм в соответствии с этим добавлением:

operators = {
    "+": {precedence: 1, associative: "left"},
    "-": {precedence: 1, associative: "left"},
    "*": {precedence: 2, associative: "left"},
    "/": {precedence: 2, associative: "left"},
    "^": {precedence: 3, associative: "right"},
    "~": {precedence: 3, associative: "right"}
}

rpn = []
stack = []
prev = null
expect = "operand" // ожидаемое состояние

for token in tokens:
    if token is a constant, number or variable:
        assert expect is "operand"
        rpn.push(token)
        expect = "operator"

    elif token is a function:
        assert expect is "operand"
        stack.push(token)
        expect = "(" // после функции ожидаем только открывающую скобку

    elif token is a delimeter:
        assert expect is "operator"

        while (stack.top() is not "("):
            rpn.push(stack.pop())

        assert stack is not empty
        expect = "operand"

    elif token is "-" operator and prev is null, operator, delimeter or "(":
        assert expect is "operand"
        stack.push("~")
        expect = "operand"

    elif token is an operator:
        assert expect is "operator"

        while (stack.top() is an operator and (stack.top() has greater precedence than token or (stack.top() and token have the same precedence and token is left-associative)):
            rpn.push(stack.pop())

        stack.push(token)
        expect = "operand"

    elif token is "(":
        assert expect is "(" or "operand"
        stack.push(token)
        expect = "operand"

    elif token is ")":
        assert expect is "operator"

        while (stack.top() is not "("):
            rpn.push(stack.pop())

        assert stack is not empty
        stack.pop()

        if stack.top() is function:
            rpn.push(stack.pop())

        expect = "operator"

    prev = token

// за концом выражения ожидаем только оператор
assert expect is "operator"

while (stack is not empty):
    assert stack.top() is not "("
    rpn.push(stack.pop())

Рассмотрим несколько выражений и ошибки, которые будут пойманы этим расширением:

Выражение	Результат
* 2 + 3	ожидался операнд, а получен оператор (*)
4 * + 3	ожидался операнд, а получен оператор (+)
3 4 +	ожидался оператор, а получен операнд (4)
sin 5	ожидалась открывающая скобка, а получен операнд (5)
max (, 5)	ожидался операнд, а получен разделитель (,)

Вроде бы всё хорошо, да? Да, но не совсем. Этот механизм надёжно ловит ошибки порядка токенов, но у него есть ограничение: он не умеет проверять, что функции вызываются с нужным числом аргументов. То есть, выражение min(2) или sin(1, 2, 3, 4) будет пропущено, хотя по смыслу является некорректным.

Контроль количества аргументов функций

Чтобы отслеживать подобные ошибки, нужно ввести дополнительный стек arity_stack, в котором будет храниться количество обработанных аргументов функции:

• Встречая функцию в этот стек добавляется значение 1 – предполагается, что за открывающей скобкой сразу начнётся первый аргумент. Если аргументов вовсе нет, это будет выявлено позже, при проверке expect на закрывающей скобке.

• Каждый раз, когда встречается разделитель (,), значение на вершине стека увеличивается на единицу. При этом важно предварительно убедиться, что стек не пуст – иначе запятая использована вне контекста вызова функции.

• Когда функция выталкивается из стека операторов, из стека аргументов извлекается соответствующее число аргументов. Затем оно сравнивается с ожидаемым количеством аргументов вытолкнутой функции: несовпадение сигнализирует об ошибке.

В таком случае окончательный алгоритм сортировочной станции будет выглядеть так:

operators = {
    "+": {precedence: 1, associative: "left"},
    "-": {precedence: 1, associative: "left"},
    "*": {precedence: 2, associative: "left"},
    "/": {precedence: 2, associative: "left"},
    "^": {precedence: 3, associative: "right"},
    "~": {precedence: 3, associative: "right"}
}

functions = {
    "sin": {arity: 1},
    "cos": {arity: 1},
    "tan": {arity: 1},
    "max": {arity: 2},
    ...
}

rpn = []
stack = []
prev = null
stack_arity = [] // стек аргументов
expect = "operand"

for token in tokens:
    if token is a constant, number or variable:
        assert expect is "operand"
        rpn.push(token)
        expect = "operator"

    elif token is a function:
        assert expect is "operand"
        stack.push(token)
        stack_arity.push(1) // добавляем один "аргумент"
        expect = "("

    elif token is a delimeter:
        assert expect is "operator"

        while (stack.top() is not "("):
            rpn.push(stack.pop())

        assert stack is not empty
        assert stack_arity is not empty // иначе запятая использована вне контекста вызова функции
        stack_arity.top() += 1 // увеличиваем количество аргументов функции
        expect = "operand"

    elif token is "-" operator and prev is null, operator, delimeter or "(":
        assert expect is "operand"
        stack.push("~")
        expect = "operand"

    elif token is operator:
        assert expect is "operator"

        while (stack.top() is operator and (stack.top() has greater precedence than token or (stack.top() and token have the same precedence and token is left-associative)):
            rpn.push(stack.pop())

        stack.push(token)
        expect = "operand"

    elif token is "(":
        assert expect is "(" or "operand"
        stack.push(token)
        expect = "operand"

    elif token is ")":
        assert expect is "operator"

        while (stack.top() is not "("):
            rpn.push(stack.pop())

        assert stack is not empty
        stack.pop()

        if stack.top() is a function:
            assert stack_arity.pop() is equal to functions[stack.top()].arity // проверяем совпадение количества аргументов
            rpn.push(stack.pop())

        expect = "operator"

    prev = token

assert expect is "operator"
assert stack_arity is empty // опциональная проверка, которую можно не делать

while (stack is not empty):
    assert stack.top() is not "("
    rpn.push(stack.pop())

Пример разбора некорректного выражения

Посмотрим, как именно работает алгоритм на выражении sin(1, 2, 3):

Токен	Действие	stack	arity_stack	rpn
sin	кладём sin в стек операторов и 1 в аргументов	[sin]	[1]	[]
(	кладём ( в стек	[sin (]	[1]	[]
1	кладём 1 в rpn	[sin (]	[1]	[1]
,	увеличиваем вершину стека аргументов на 1	[sin (]	[2]	[1]
2	кладём 2 в rpn	[sin (]	[2]	[1 2]
,	увеличиваем вершину стека аргументов на 1	[sin (]	[3]	[1 2]
3	кладём 3 в rpn	[sin (]	[3]	[1 2 3]
)	извлекаем из стека операторов (	[sin]	[3]	[1 2 3]
	достаём 3 из стека аргументов	[sin]	[]	[1 2 3]
	проверяем ожидаемое количество аргументов функции sin и 3	[sin]	[]	[1 2 3]
	сообщаем об ошибке с некорректным числом аргументов

Теперь проблема с несовпадающим числом аргументов решена и алгоритм сообщит о любых синтаксических ошибках во входном выражении:

Выражение	Результат
min()	Ожидался операнд, но получена закрывающая скобка ())
min(2)	Функция min принимает 2 аргумента, а не один
sin(1, 2, 3, 4)	Функция sin принимает один аргумент, а не четыре
max(1, 2)	1 2 max
sin(5)	5 sin

Заключение

Алгоритм сортировочной станции, несмотря на свою простоту и эффективность, в своей классической форме не проверяет корректность входного выражения. Подавляющее число авторов статей, объясняющих этот алгоритм, и вовсе зачастую ограничиваются лишь простыми выражениями, не рассматривая порой даже обработку возведения в степень.

Мы рассмотрели, как с помощью небольших модификаций можно добавить проверку на чередование операндов и операторов, а также корректность числа аргументов для функций. Эти изменения позволяют сделать алгоритм надёжным и обеспечивают более информативную диагностику ошибок на лету, не прибегая к дополнительным фазам разбора.

Для тех, кто хочет углубиться в тонкости работы с математическими выражениями и реализации алгоритмов обработки ошибок, на моём сайте (а не в телеграм канале, как можно было бы подумать) можно найти небольшой цикл статей о парсинге математических выражений от токенизации до вычисления с реализацией как парсера, использующего алгоритм сортировочной станции, так и парсера рекурсивного спуска и элегантного парсера Пратта.