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

Алгоритм сортировочной станции
Сорт	Разбор
Структура данных	Куча
Худший вариант производительности	О ( н ) {\displaystyle O(n)}
Наихудшая сложность пространства	О ( н ) {\displaystyle O(n)}

Алгоритм преобразования синтаксиса с инфиксной нотацией в постфиксную

В информатике алгоритм сортировочной станции — это метод разбора арифметических или логических выражений или их комбинации, указанных в инфиксной нотации . Он может создавать либо строку постфиксной нотации, также известную как обратная польская нотация ( RPN), либо абстрактное синтаксическое дерево (AST). ^[1] Алгоритм был изобретен Эдсгером Дейкстрой , впервые опубликован в ноябре 1961 года ^[2] и назван алгоритмом «сортировочной станции», поскольку его работа напоминает работу сортировочной станции на железной дороге .

Как и оценка RPN, алгоритм сортировочной станции основан на стеке . Инфиксные выражения — это форма математической записи, к которой привыкло большинство людей, например, «3 + 4» или «3 + 4 × (2 − 1)» . Для преобразования есть две текстовые переменные ( строки ), входная и выходная. Также есть стек , который хранит операторы, еще не добавленные в выходную очередь. Для преобразования программа считывает каждый символ по порядку и делает что-то на основе этого символа. Результатом для приведенных выше примеров будет (в обратной польской нотации ) «3 4 +» и «3 4 2 1 − × +» соответственно.

Алгоритм сортировочной станции правильно проанализирует все допустимые инфиксные выражения, но не отклонит все недопустимые выражения. Например, "1 2 +" не является допустимым инфиксным выражением, но будет проанализировано как "1 + 2" . Однако алгоритм может отклонить выражения с непарными скобками.

Алгоритм сортировочной станции позднее был обобщен до анализа приоритета операторов .

Простое преобразование

Вход: 3 + 4
Поместить 3 в очередь вывода (всякий раз, когда число считывается, оно помещается в очередь вывода)
Вставьте + (или его идентификатор) в стек операторов.
Поместить 4 в очередь вывода
После прочтения выражения извлеките операторы из стека и добавьте их к выводу.
В данном случае есть только один знак «+».
Выход: 3 4 +

Это уже демонстрирует несколько правил:

Все числа при считывании выводятся на выход.
В конце чтения выражения извлеките все операторы из стека и поместите их на выход.

Графическая иллюстрация

Графическая иллюстрация алгоритма с использованием трехстороннего железнодорожного узла . Входные данные обрабатываются по одному символу за раз: если найдена переменная или число, они копируются непосредственно на выход a), c), e), h). Если символ является оператором, он помещается в стек операторов b), d), f). Если приоритет оператора ниже, чем у операторов наверху стека, или приоритеты равны, и оператор слева ассоциативен, то этот оператор извлекается из стека и добавляется к выходу g). Наконец, все оставшиеся операторы извлекаются из стека и добавляются к выходу i).

Алгоритм в деталях

/* Функции, упомянутые в этом алгоритме, являются простыми функциями с одним аргументом, такими как синус, обратная функция или факториал. */ /* Эта реализация не реализует составные функции, функции с переменным числом аргументов или унарные операторы. */в то время как есть жетоны, которые нужно прочитать: прочитать токен если токен: - число : поместить его в очередь вывода - функция : поместить его в стек оператора - оператор  o ₁ : while (наверху стека операторов находится оператор o _{2 , который не является левой скобкой,}и ( o ₂ имеет больший приоритет, чем o ₁ или ( o ₁ и o ₂ имеют одинаковый приоритет , а  o ₁ является левоассоциативным)) ): вытолкнуть o ₂ из стека операторов в выходную очередь вставьте o ₁ в стек оператора - "," : пока оператор наверху стека операторов не является левой скобкой: вытащить оператор из стека операторов в выходную очередь - левая скобка (т.е. "("): поместить его в стек оператора - правая скобка (т.е. ")"): в то время как оператор наверху стека операторов не является левой скобкой: { утверждать, что стек операторов не пуст} /* Если стек заканчивается, а левая скобка не найдена, значит, есть несовпадающие скобки. */ вытащить оператор из стека операторов в выходную очередь { утверждаем, что наверху стека операторов есть левая скобка} извлечь левую скобку из стека операторов и отбросить ее если наверху стека операторов находится токен функции, то : вытащить функцию из стека операторов в очередь вывода/* После цикла while выталкиваем оставшиеся элементы из стека операторов в выходную очередь. */ пока есть токены в стеке операторов: /* Если токен оператора наверху стека является скобкой, то есть несовпадающие скобки. */ { assert the Operator on the top of stack is not a (left) roundthesis} вытащить оператор из стека операторов в выходную очередь

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

Алгоритм сортировочной станции также может быть применен для создания префиксной нотации (также известной как польская нотация ). Для этого нужно просто начать с конца строки токенов, которые нужно проанализировать, и двигаться в обратном направлении, перевернуть выходную очередь (тем самым сделав выходную очередь выходным стеком) и поменять местами поведение левой и правой скобок (помня, что поведение теперь левой скобки должно выскакивать, пока не найдется теперь правая скобка). И изменить условие ассоциативности на правое.

Подробные примеры

Вход: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3

Оператор	Приоритет	Ассоциативность
^	4	Верно
×	3	Левый
÷	3	Левый
+	2	Левый
−	2	Левый

Символ ^ представляет оператор возведения в степень .

Токен	Действие	Выход (в RPN )	Стек операторов	Примечания
3	Добавить токен к выходу	3
+	Поместить токен в стек	3	+
4	Добавить токен к выходу	3 4	+
×	Поместить токен в стек	3 4	× +	× имеет более высокий приоритет, чем +
2	Добавить токен к выходу	3 4 2	× +
÷	Извлечь стек для вывода	3 4 2 ×	+	÷ и × имеют одинаковый приоритет
÷	Поместить токен в стек	3 4 2 ×	÷ +	÷ имеет более высокий приоритет, чем +
(	Поместить токен в стек	3 4 2 ×	( ÷ +
1	Добавить токен к выходу	3 4 2 × 1	( ÷ +
−	Поместить токен в стек	3 4 2 × 1	− ( ÷ +
5	Добавить токен к выходу	3 4 2 × 1 5	− ( ÷ +
)	Извлечь стек для вывода	3 4 2 × 1 5 −	( ÷ +	Повторяется до тех пор, пока не будет найдено "("
)	Поп-стек	3 4 2 × 1 5 −	÷ +	Удалить соответствующие скобки
^	Поместить токен в стек	3 4 2 × 1 5 −	^ ÷ +	^ имеет более высокий приоритет, чем ÷
2	Добавить токен к выходу	3 4 2 × 1 5 − 2	^ ÷ +
^	Поместить токен в стек	3 4 2 × 1 5 − 2	^ ^ ÷ +	^ вычисляется справа налево
3	Добавить токен к выходу	3 4 2 × 1 5 − 2 3	^ ^ ÷ +
конец	Извлечь весь стек для вывода	3 4 2 × 1 5 − 2 3 ^ ^ ÷ +

Ввод: sin (max (2, 3) ÷ 3 × $π$ )

Токен	Действие	Выход (в RPN )	Стек операторов	Примечания
грех	Поместить токен в стек		грех
(	Поместить токен в стек		( грех
макс	Поместить токен в стек		макс ( грех
(	Поместить токен в стек		( макс ( грех
2	Добавить токен к выходу	2	( макс ( грех
,	Игнорировать	2	( макс ( грех	Оператор наверху стека — левая скобка.
3	Добавить токен к выходу	2 3	( макс ( грех
)	Извлечь стек для вывода	2 3	( макс ( грех	Повторяется до тех пор, пока "(" не окажется наверху стека
Поп-стек	2 3	макс ( грех	Отбрасывание парных скобок
Извлечь стек для вывода	2 3 макс.	( грех	Функция на вершине стека
÷	Поместить токен в стек	2 3 макс.	÷ ( грех
3	Добавить токен к выходу	2 3 макс 3	÷ ( грех
×	Извлечь стек для вывода	2 3 макс 3 ÷	( грех
×	Поместить токен в стек	2 3 макс 3 ÷	× ( грех
$π$	Добавить токен к выходу	2 3 макс 3 ÷ $π$	× ( грех
)	Извлечь стек для вывода	2 3 макс 3 ÷ $π$ ×	( грех	Повторяется до тех пор, пока "(" не окажется наверху стека
	Поп-стек	2 3 макс 3 ÷ $π$ ×	грех	Отбрасывание парных скобок
	Извлечь стек для вывода	2 3 макс 3 ÷ $π$ × синус		Функция на вершине стека
конец	Извлечь весь стек для вывода	2 3 макс 3 ÷ $π$ × синус

Смотрите также

Ссылки

^ Теодор Норвелл (1999). «Анализ выражений методом рекурсивного спуска». www.engr.mun.ca . Получено 28.12.2020 .
^ Дейкстра, Эдсгер (1 ноября 1961). «Перевод Алгола 60: Транслятор Алгола 60 для X1 и создание переводчика для Алгола 60». Stichting Mathematich Centrum .

Внешние ссылки

Оригинальное описание алгоритма сортировочной станции Дейкстрой
Реализация грамотных программ на языке C
Демонстрация алгоритма сортировочной станции в Rust
Java-апплет, демонстрирующий алгоритм сортировочной станции
Виджет Silverlight, демонстрирующий алгоритм сортировочной станции и оценку арифметических выражений
Код Matlab, оценка арифметических выражений с использованием алгоритма маневровой станции

[1] Теодор Норвелл (1999). «Анализ выражений методом рекурсивного спуска». www.engr.mun.ca . Получено 28.12.2020 .

[2] Дейкстра, Эдсгер (1 ноября 1961). «Перевод Алгола 60: Транслятор Алгола 60 для X1 и создание переводчика для Алгола 60». Stichting Mathematich Centrum .