В информатике алгоритм сортировочной станции — это метод разбора арифметических или логических выражений или их комбинации, указанных в инфиксной нотации . Он может создавать либо строку постфиксной нотации, также известную как обратная польская нотация ( RPN), либо абстрактное синтаксическое дерево (AST). [1] Алгоритм был изобретен Эдсгером Дейкстрой , впервые опубликован в ноябре 1961 года [2] и назван алгоритмом «сортировочной станции», поскольку его работа напоминает работу сортировочной станции на железной дороге .
Как и оценка RPN, алгоритм сортировочной станции основан на стеке . Инфиксные выражения — это форма математической записи, к которой привыкло большинство людей, например, «3 + 4» или «3 + 4 × (2 − 1)» . Для преобразования есть две текстовые переменные ( строки ), входная и выходная. Также есть стек , который хранит операторы, еще не добавленные в выходную очередь. Для преобразования программа считывает каждый символ по порядку и делает что-то на основе этого символа. Результатом для приведенных выше примеров будет (в обратной польской записи ) «3 4 +» и «3 4 2 1 − × +» соответственно.
Алгоритм сортировочной станции правильно проанализирует все допустимые инфиксные выражения, но не отклонит все недопустимые выражения. Например, "1 2 +" не является допустимым инфиксным выражением, но будет проанализировано как "1 + 2" . Однако алгоритм может отклонить выражения с непарными скобками.
Алгоритм сортировочной станции позднее был обобщен до анализа приоритета операторов .
Это уже демонстрирует несколько правил:
Графическая иллюстрация алгоритма с использованием трехстороннего железнодорожного узла . Входные данные обрабатываются по одному символу за раз: если найдена переменная или число, они копируются непосредственно на выход a), c), e), h). Если символ является оператором, он помещается в стек операторов b), d), f). Если приоритет оператора ниже, чем у операторов наверху стека, или приоритеты равны, и оператор слева ассоциативен, то этот оператор извлекается из стека и добавляется к выходу g). Наконец, все оставшиеся операторы извлекаются из стека и добавляются к выходу i).
/* Функции, упомянутые в этом алгоритме, являются простыми функциями с одним аргументом, такими как синус, обратная функция или факториал. */ /* Эта реализация не реализует составные функции, функции с переменным числом аргументов или унарные операторы. */в то время как есть жетоны, которые нужно прочитать: прочитать токен если токен: - число : поместить его в очередь вывода - функция : поместить его в стек оператора - оператор o 1 : while (наверху стека операторов находится оператор o 2 , который не является левой скобкой, и ( o 2 имеет больший приоритет, чем o 1 или ( o 1 и o 2 имеют одинаковый приоритет , а o 1 является левоассоциативным)) ): вытолкнуть o 2 из стека операторов в выходную очередь вставьте o 1 в стек оператора - "," : пока оператор наверху стека операторов не является левой скобкой: извлечь оператор из стека операторов в выходную очередь - левая скобка (т.е. "("): поместить его в стек оператора - правая скобка (т.е. ")"): в то время как оператор наверху стека операторов не является левой скобкой: { утверждать, что стек операторов не пуст} /* Если стек заканчивается, а левая скобка не найдена, значит, имеются несовпадающие скобки. */ извлечь оператор из стека операторов в выходную очередь { утверждаем, что наверху стека операторов есть левая скобка} извлечь левую скобку из стека операторов и отбросить ее если наверху стека операторов находится токен функции, то : вытащить функцию из стека операторов в очередь вывода/* После цикла while выталкиваем оставшиеся элементы из стека операторов в выходную очередь. */ пока есть токены в стеке операторов: /* Если токен оператора наверху стека является скобкой, то есть несовпадающие скобки. */ { assert the Operator on the top of stack is not a (left) roundthesis} вытащить оператор из стека операторов в выходную очередь
Чтобы проанализировать сложность времени выполнения этого алгоритма, нужно только отметить, что каждый токен будет прочитан один раз, каждое число, функция или оператор будут выведены один раз, и каждая функция, оператор или скобка будут помещены в стек и извлечены из стека один раз — следовательно, существует не более постоянного числа операций, выполняемых на один токен, и время выполнения, таким образом, составляет O( n ) — линейно по размеру входных данных.
Алгоритм сортировочной станции также может быть применен для создания префиксной нотации (также известной как польская нотация ). Для этого нужно просто начать с конца строки токенов, которые нужно проанализировать, и двигаться в обратном направлении, перевернуть выходную очередь (тем самым сделав выходную очередь выходным стеком) и поменять местами поведение левой и правой скобок (помня, что поведение теперь левой скобки должно выскакивать, пока не найдется теперь правая скобка). И изменить условие ассоциативности на правое.
Вход: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3
Символ ^ представляет оператор возведения в степень .
Ввод: sin (max (2, 3) ÷ 3 × π )