Алгоритм преобразования инфиксной нотации в постфиксную (алгоритм сортировочной станции)
Shunting yard algorithm
Алгоритм сортировочной станции (Shunting Yard) – преобразование выражений из инфиксной нотации в постфиксную (RPN). Разработан Э. Дейкстрой, основан на стеке.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Алгоритм преобразования синтаксиса из инфиксной нотации в постфиксную нотацию
Algorithm to parse a syntax with infix notation to postfix notation
В информатике алгоритм сортировочной станции — это метод разбора арифметических или логических выражений, или их комбинации, заданных в инфиксной нотации. Он может генерировать либо строку в постфиксной нотации, также известной как обратная польская нотация (RPN), либо абстрактное синтаксическое дерево (AST). Алгоритм был изобретен Эдсгером Дейкстрой и назван алгоритмом «сортировочной станции», поскольку его работа напоминает работу железнодорожной сортировочной станции. Дейкстра впервые описал алгоритм сортировочной станции в отчете Mathematisch Centrum MR 34/61. Как и вычисление RPN, алгоритм сортировочной станции основан на стеке. Инфиксные выражения — это форма математической записи, к которой привыкли большинство людей, например, «3 + 4» или «3 + 4 × (2 − 1)». Для преобразования используются две текстовые переменные (строки): входные данные и выходные данные. Также используется стек, который хранит операторы, еще не добавленные в выходную очередь. Для преобразования программа последовательно считывает каждый символ и выполняет определенное действие в зависимости от этого символа. Результатом для приведенных выше примеров (в обратной польской нотации) будут «3 4 +» и «3 4 2 1 − × +» соответственно. Алгоритм сортировочной станции правильно разбирает все допустимые инфиксные выражения, но не отклоняет все недопустимые выражения. Например, «1 2 +» не является допустимым инфиксным выражением, но будет разобрано как «1 + 2». Однако алгоритм может отклонить выражения с несбалансированными скобками. Алгоритм сортировочной станции впоследствии был обобщен в разбор с учетом приоритета операторов.
In computer science, the shunting yard algorithm is a method for parsing arithmetical or logical expressions, or a combination of both, specified in infix notation. It can produce either a postfix notation string, also known as Reverse Polish notation (RPN), or an abstract syntax tree (AST). The algorithm was invented by Edsger Dijkstra and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard. Dijkstra first described the shunting yard algorithm in the Mathematisch Centrum report MR 34/61. Like the evaluation of RPN, the shunting yard algorithm is stack based. Infix expressions are the form of mathematical notation most people are used to, for instance "3 + 4" or "3 + 4 × (2 − 1)". For the conversion there are two text variables (strings), the input and the output. There is also a stack that holds operators not yet added to the output queue. To convert, the program reads each symbol in order and does something based on that symbol. The result for the above examples would be (in Reverse Polish notation) "3 4 +" and "3 4 2 1 − × +", respectively. The shunting yard algorithm will correctly parse all valid infix expressions, but does not reject all invalid expressions. For example, "1 2 +" is not a valid infix expression, but would be parsed as "1 + 2". The algorithm can however reject expressions with mismatched parentheses. The shunting yard algorithm was later generalized into operator precedence parsing.
Графическая иллюстрация
Графическая иллюстрация алгоритма, использующая трехпутный железнодорожный перекресток. Вход обрабатывается по одному символу за раз: если найден символ, являющийся переменной или числом, он копируется непосредственно в выход a), c), e), h). Если символ является оператором, он помещается в стек операторов b), d), f). Если приоритет оператора ниже приоритета операторов на вершине стека или приоритеты равны и оператор является левоассоциативным, то этот оператор извлекается из стека и добавляется в выход g). Наконец, все оставшиеся операторы извлекаются из стека и добавляются в выход i).
Graphical illustration of algorithm, using a three way railroad junction. The input is processed one symbol at a time: if a variable or number is found, it is copied directly to the output a), c), e), h). If the symbol is an operator, it is pushed onto the operator stack b), d), f). If the operator's precedence is lower than that of the operators at the top of the stack or the precedences are equal and the operator is left associative, then that operator is popped off the stack and added to the output g). Finally, any remaining operators are popped off the stack and added to the output i).