В информатике , то алгоритм сортировочной станции является метод для разбора математических выражений , указанных в инфиксной нотации . Он может создавать либо строку постфиксной нотации, также известную как обратная польская нотация (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» . Однако алгоритм может отклонять выражения с несовпадающими скобками.
Алгоритм маневровой станции позже был обобщен на анализ приоритета операторов .
Простое преобразование
- Ввод: 3 + 4
- Нажать 3 в очередь вывода (всякий раз, когда число читается, оно отправляется на вывод)
- Вставьте + (или его идентификатор) в стек оператора
- Нажмите 4 в очередь вывода
- После прочтения выражения извлеките операторы из стека и добавьте их к выходным данным.
- В этом случае есть только один «+».
- Выход: 3 4 +
Это уже показывает пару правил:
- При чтении все числа отправляются на выход.
- В конце чтения выражения перенесите все операторы из стека в выходные данные.
Графическая иллюстрация
![Shunting yard.svg](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/2/24/Shunting_yard.svg/400px-Shunting_yard.svg.png)
Графическая иллюстрация алгоритма с использованием трехстороннего железнодорожного узла . Вход обрабатывается по одному символу за раз: если переменная или число найдены, они копируются непосредственно на выход a), c), e), h). Если символ является оператором, он помещается в стек операторов b), d), f). Если приоритет оператора ниже, чем приоритет операторов наверху стека, или если прецеденты равны и оператор остается ассоциативным, то этот оператор извлекается из стека и добавляется к выходу g). Наконец, все оставшиеся операторы извлекаются из стека и добавляются к выводу i).
Подробно об алгоритме
Важные термины: токен , функция , ассоциативность оператора , приоритет
/ * Эта реализация не реализует составные функции, функции с переменным числом аргументов и унарные операторы. * /пока есть жетоны, которые нужно прочитать: прочитать жетон если токен: - номер : поместите его в очередь вывода - функция : поместите его в стек операторов - оператор o 1 : while ( кроме левой круглой скобки есть оператор o 2 наверху стека операторов, а o 2 имеет больший приоритет чем o 1 или o 2 левоассоциативны): pop o 2 из стека операторов в очередь вывода поместите o 1 в стек операторов - левая скобка (т.е. "("): поместите его в стек операторов - правая скобка (т.е. ")"): в то время как оператор в верхней части стека операторов не является левой скобкой: поместить оператор из стека операторов в очередь вывода / * Если стек исчерпывается, а левая скобка не найдена, значит, скобки не совпадают. * / { утверждают, что вверху стека операторов стоит левая скобка} вытащить левую скобку из стека операторов и отбросить ее если в верхней части стека операторов есть токен функции, то : поместить функцию из стека операторов в очередь вывода/ * После цикла while вставляем оставшиеся элементы из стека операторов в очередь вывода. * / при наличии токенов в стеке операторов: / * Если токен оператора в верхней части стека является круглой скобкой, то круглые скобки не совпадают. * / { утверждение, что оператор наверху стека не является (левой) круглой скобкой} поместить оператор из стека операторов в очередь вывода
Чтобы проанализировать временную сложность этого алгоритма, нужно только отметить, что каждый токен будет прочитан один раз, каждое число, функция или оператор будут напечатаны один раз, а каждая функция, оператор или скобка будут помещены в стек и выскакивает из стека один раз - следовательно, на каждый токен выполняется не более постоянного числа операций, и время выполнения, таким образом, 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
Смотрите также
Рекомендации
- ^ Теодор Норвелл (1999). «Анализ выражений с помощью рекурсивного спуска» . www.engr.mun.ca . Проверено 28 декабря 2020 .
Внешние ссылки
- Оригинальное описание алгоритма маневрового двора Дейкстры
- Грамотная реализация программ на C
- Java-апплет, демонстрирующий алгоритм маневрового двора
- Виджет Silverlight, демонстрирующий алгоритм маневрового двора и вычисление арифметических выражений
- Анализ выражений методом рекурсивного спуска Теодор Норвелл © 1999–2001. Дата доступа 14 сентября 2006 г.
- Код Matlab, вычисление арифметических выражений с использованием алгоритма маневровой станции