Алгоритм сортировочной станции

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

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

АлгоритмПравить

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

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

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

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

• Пока присутствует на вершине стека токен оператор op2, чей приоритет выше или равен приоритету op1, и при равенстве приоритетов op1 является левоассоциативным:
  • Переложить op2 из стека в выходную очередь;
• Положить op1 в стек.

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

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

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

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

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

• Конец.

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

СсылкиПравить

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