Просмотр кода страницы Алгоритм сортировочной станции

'''Алгоритм сортировочной станции''' — способ разбора математических выражений, представленных в [[инфиксная нотация|инфиксной нотации]]. Может быть использован для получения вывода в виде [[Обратная польская запись|обратной польской нотации]] или в виде [[Абстрактное синтаксическое дерево|абстрактного синтаксического дерева]]. Алгоритм предложен [[Эдсгер Дейкстра|Эдсгером Дейкстрой]] и назван им «алгоритм сортировочной станции», поскольку напоминает действие [[Железная дорога|железнодорожной]] [[Сортировочная станция|сортировочной станции]].

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

== Алгоритм ==
[[Файл:Shunting yard-ru.svg|мини|альт=Иллюстрация алгоритма сортировочной станции|Иллюстрация алгоритма сортировочной станции]]
* Пока не все токены обработаны:

:* Прочитать [[Токен (лексический анализ)|токен]].
:* Если токен — ''число'', то добавить его в очередь вывода.
:* Если токен — ''[[функция (программирование)|функция]]'', то поместить его в стек.
:* Если токен — ''разделитель аргументов функции'' (например, запятая):
::* Пока токен на вершине стека не ''открывающая скобка:''
::**Переложить оператор из стека в выходную очередь. 
::**Если стек закончился до того, как был встречен токен ''открывающая скобка'', то в выражении пропущен ''разделитель аргументов функции'' (запятая), либо пропущена ''открывающая скобка''.
:* Если токен — ''оператор'' op1, то:
::* Пока присутствует на вершине стека токен ''оператор'' op2, чей приоритет выше или равен приоритету op1, и при равенстве приоритетов op1 является [[Очерёдность операций|левоассоциативным]]:
::**Переложить op2 из стека в выходную очередь;
::*Положить op1 в стек.
:* Если токен — ''открывающая скобка'', то положить его в стек.
:* Если токен — ''закрывающая скобка'':
::* Пока токен на вершине стека не ''открывающая скобка''
::**Переложить оператор из стека в выходную очередь.
::**Если стек закончился до того, как был встречен токен ''открывающая скобка'', то в выражении пропущена скобка.
::* Выкинуть ''открывающую скобку'' из стека, но не добавлять в очередь вывода.
::* Если токен на вершине стека — функция, переложить её в выходную очередь.
* Если больше не осталось токенов на входе:
:* Пока есть токены операторы в стеке:
::* Если токен оператор на вершине стека — ''открывающая скобка'', то в выражении пропущена скобка.
::* Переложить оператор из стека в выходную очередь.
* Конец.

Каждый токен-число, функция или оператор выводится только один раз, а также каждый токен-функция, оператор или круглая скобка будет добавлен и удалён из стека по одному разу. Постоянное количество операций на токен, линейная сложность алгоритма O(''n'').

== Ссылки ==
{{wikibooks|Реализации алгоритмов/Алгоритм сортировочной станции|Алгоритм сортировочной станции}}
* [http://www.chris-j.co.uk/parsing.php Java-апплет, демонстрирующий работу алгоритма]
* [http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm Parsing Expressions by Recursive Descent] Theodore Norvell © 1999—2001. Access date September 14, 2006.
* [https://web.archive.org/web/20090605032748/http://montcs.bloomu.edu/~bobmon/Information/RPN/infix2rpn.shtml Алгоритм преобразования инфиксной записи в обратную польскую нотацию]
* [http://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF Оригинальное описание алгоритма]{{ref-en}}
* [http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting-yard-algorithm-to-allow-variable-numbers-of-arguments-to-functions/ Расширение алгоритма для использования произвольного количества аргументов функции]
{{rq|refless}}

[[Категория:Синтаксический анализ]]