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

Алгоритм сортировочной станции
Сорт	Разбор
Структура данных	Куча
Худшая производительность
Наихудшая пространственная сложность

В информатике алгоритм сортировочной станции — это метод анализа арифметических или логических выражений или их комбинации, заданный в инфиксной записи . Он может создавать либо строку постфиксной нотации, также известную как обратная польская нотация (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 +

Это уже показывает пару правил:

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

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

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

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

/* The functions referred to in this algorithm are simple single argument functions such as sine, inverse or factorial. */
/* This implementation does not implement composite functions, functions with a variable number of arguments, or unary operators. */

while there are tokens to be read:
    read a token
    if the token is:
    - a number:
        put it into the output queue
    - a function:
        push it onto the operator stack 
    - an operator o₁:
        while (
            there is an operator o₂ at the top of the operator stack which is not a left parenthesis, 
            and (o₂ has greater precedence than o₁ or (o₁ and o₂ have the same precedence and o₁ is left-associative))
        ):
            pop o₂ from the operator stack into the output queue
        push o₁ onto the operator stack
    - a ",":
        while the operator at the top of the operator stack is not a left parenthesis:
             pop the operator from the operator stack into the output queue
    - a left parenthesis (i.e. "("):
        push it onto the operator stack
    - a right parenthesis (i.e. ")"):
        while the operator at the top of the operator stack is not a left parenthesis:
            {assert the operator stack is not empty}
            /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
            pop the operator from the operator stack into the output queue
        {assert there is a left parenthesis at the top of the operator stack}
        pop the left parenthesis from the operator stack and discard it
        if there is a function token at the top of the operator stack, then:
            pop the function from the operator stack into the output queue
/* After the while loop, pop the remaining items from the operator stack into the output queue. */
while there are tokens on the operator stack:
    /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
    {assert the operator on top of the stack is not a (left) parenthesis}
    pop the operator from the operator stack onto the output queue

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

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

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

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

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

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

Токен	Действие	Выход (в РПН )	Оператор куча	Примечания
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 × $π$ )

Токен	Действие	Выход (в РПН )	Оператор куча	Примечания
грех	Поместите токен в стек		грех
(	Поместите токен в стек		(грех
Макс	Поместите токен в стек		Макс (грех
(	Поместите токен в стек		(макс ( грех
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 ÷ $π$ × sin		Функция на вершине стека
конец	Вытащить весь стек на вывод	2 3 макс 3 ÷ $π$ × sin

См. также

Ссылки

^ Теодор Норвелл (1999). «Разбор выражений рекурсивным спуском» . www.engr.mun.ca. Проверено 28 декабря 2020 г.
^ Дейкстра, редактор (1 ноября 1961 г.). Algol 60 для X1». «Перевод Algol 60: переводчик Учреждение Математического центра

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

[1] Теодор Норвелл (1999). «Разбор выражений рекурсивным спуском» . www.engr.mun.ca. Проверено 28 декабря 2020 г.

[2] Дейкстра, редактор (1 ноября 1961 г.). Algol 60 для X1». «Перевод Algol 60: переводчик Учреждение Математического центра

[1]

[2]

v т и Алгоритмы разбора
Сверху вниз	Эрли LL Рекурсивный спуск Хвостовая рекурсия
Вверх дном	Приоритет Простой Оператор Маневровый двор ЛР Простой смотреть вперед Канонический Обобщенный ГАЛОЧКА Рекурсивное восхождение Shift-уменьшить
Смешанное, другое	Комбинатор Диаграмма Левый угол Статистический
Связанные темы	ПЭГ Определенная грамматика предложения Детерминированный анализ Динамическое программирование Мемоизация Генератор парсера ЛАЛР Дерево разбора АСТ Бессканерный парсинг История создания компилятора Сравнение генераторов парсеров Грамматика приоритета операторов