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

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

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

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

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

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.