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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Алгоритм[править | править вики-текст]

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

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

Ссылки[править | править вики-текст]