Маневровый алгоритм

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Август 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

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

   В этом случае есть только один «+».

6. Выход: 3 4 +

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

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

Графическая иллюстрация [ править ]

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

Подробно об алгоритме [ править ]

Важные термины: токен , функция , ассоциативность оператора , приоритет

/ * Эта реализация не реализует составные функции, функции с переменным числом аргументов и унарные операторы. * /пока есть жетоны, которые нужно прочитать: прочитать жетон. если токен является числом, то : поместите его в очередь вывода. иначе, если токен является функцией, тогда : поместите его в стек операторов  иначе, если токен является оператором, то : while ((есть оператор в верхней части стека операторов) и ((оператор в верхней части стека операторов имеет больший приоритет) или (оператор в верхней части оператора стек имеет равный приоритет, и токен остается ассоциативным)) и (оператор в верхней части стека операторов не является левой круглой скобкой)): вставлять операторы из стека операторов в очередь вывода. поместите его в стек оператора. иначе, если токен является левой круглой скобкой (например, "("), то : поместите его в стек оператора. иначе, если токен является правой круглой скобкой (т.е. ")"), тогда : пока оператор в верхней части стека операторов не является левой круглой скобкой: поместить оператора из стека операторов в очередь вывода. / * Если стек исчерпывается, а левая скобка не найдена, значит, скобки не совпадают. * /  если в верхней части стека операторов стоит левая скобка, то : вытащить оператор из стека операторов и отбросить его если в верхней части стека операторов есть токен функции, то : поместить функцию из стека операторов в очередь вывода./ * После цикла while, если стек оператора не равен нулю, поместить все в очередь вывода * /, если больше нет токенов для чтения, тогда : пока в стеке еще есть токены операторов: / * Если токен оператора наверху stack - круглые скобки, значит, круглые скобки не совпадают. * / поместить оператора из стека операторов в очередь вывода.выход.

Чтобы проанализировать временную сложность этого алгоритма, нужно только отметить, что каждый токен будет прочитан один раз, каждое число, функция или оператор будут напечатаны один раз, а каждая функция, оператор или скобка будут помещены в стек и выскакивает из стека один раз - следовательно, на каждый токен выполняется не более постоянного числа операций, и время выполнения, таким образом, 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 (макс (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 ÷ π × sin

См. Также [ править ]

• Парсер приоритета операторов
• Перестановка, сортируемая стеком

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

Внешние ссылки [ править ]

• Оригинальное описание алгоритма маневрового двора Дейкстры
• Грамотная реализация программ на C
• Java-апплет, демонстрирующий алгоритм маневрового двора
• Виджет Silverlight, демонстрирующий алгоритм маневрового двора и вычисление арифметических выражений
• Анализ выражений методом рекурсивного спуска Теодор Норвелл © 1999–2001. Дата доступа 14 сентября 2006 г.
• Код Matlab, вычисление арифметических выражений с использованием алгоритма маневровой станции