WikiSort.ru - Не сортированное

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

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

Алгоритм

• Пока не все токены обработаны:

• Прочитать токен.
• Если токен — число, то добавить его в очередь вывода.
• Если токен — функция, то поместить его в стек.
• Если токен — разделитель аргументов функции (например запятая):

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

• Если токен — оператор op1, то:

• Пока присутствует на вершине стека токен оператор op2, и

Либо оператор op1 лево-ассоциативен и его приоритет меньше, чем у оператора op2 либо равен,

или оператор op1 право-ассоциативен и его приоритет меньше, чем у op2,

переложить op2 из стека в выходную очередь;

• (Иначе, когда стек операторов пуст или содержит открывающую скобку)
  • положить op1 в стек.

• Если токен — открывающая скобка, то положить его в стек.
• Если токен — закрывающая скобка:

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

• Если больше не осталось токенов на входе:

• Пока есть токены операторы в стеке:

• Если токен оператор на вершине стека — скобка, то в выражении присутствует незакрытая скобка.
• Переложить оператор из стека в выходную очередь.

• Конец.

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

Ссылки

Имеется викиучебник по теме
«Алгоритм сортировочной станции»

• Java апплет, демонстрирующий работу алгоритма
• Parsing Expressions by Recursive Descent Theodore Norvell © 1999—2001. Access date September 14, 2006.
• Алгоритм преобразования инфиксной записи в обратную польскую нотацию
• Оригинальное описание алгоритма
• Расширение алгоритма для использования произвольного количества аргументов функции

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.