Алгоритм сортировочной станции — способ разбора математических выражений, представленных в инфиксной нотации. Может быть использован для получения вывода в виде обратной польской нотации или в виде абстрактного синтаксического дерева. Алгоритм предложен Эдсгером Дейкстрой и назван им «алгоритм сортировочной станции», поскольку напоминает действие железнодорожной сортировочной станции.
Так же, как и вычисление значений выражений в обратной польской записи, алгоритм работает при помощи стека. Инфиксная запись математических выражений чаще всего используется людьми, её примеры: 2+4 и 3+6*(3-2). Для преобразования в обратную польскую нотацию используется 2 строки: входная и выходная, и стек для хранения операторов, ещё не добавленных в выходную очередь. При преобразовании алгоритм считывает 1 символ и производит действия, зависящие от данного символа.
Алгоритм
Пока не все токены обработаны:
Прочитать токен. Если токен — число, то добавить его в очередь вывода. Если токен — функция, то поместить его в стек. Если токен — разделитель аргументов функции (например, запятая): Пока токен на вершине стека не открывающая скобка: Переложить оператор из стека в выходную очередь. Если стек закончился до того, как был встречен токен открывающая скобка, то в выражении пропущен разделитель аргументов функции (запятая), либо пропущена открывающая скобка. Если токен — оператор op1, то: Пока присутствует на вершине стека токен оператор op2, чей приоритет выше или равен приоритету op1, и при равенстве приоритетов op1 является левоассоциативным: Переложить op2 из стека в выходную очередь; Положить op1 в стек. Если токен — открывающая скобка, то положить его в стек. Если токен — закрывающая скобка: Пока токен на вершине стека не открывающая скобка Переложить оператор из стека в выходную очередь. Если стек закончился до того, как был встречен токен открывающая скобка, то в выражении пропущена скобка. Выкинуть открывающую скобку из стека, но не добавлять в очередь вывода. Если токен на вершине стека — функция, переложить её в выходную очередь. Если больше не осталось токенов на входе: Пока есть токены операторы в стеке: Если токен оператор на вершине стека — открывающая скобка, то в выражении пропущена скобка. Переложить оператор из стека в выходную очередь. Конец.
Каждый токен-число, функция или оператор выводится только один раз, а также каждый токен-функция, оператор или круглая скобка будет добавлен и удалён из стека по одному разу. Постоянное количество операций на токен, линейная сложность алгоритма O(n).
Ссылки
Java-апплет, демонстрирующий работу алгоритма Parsing Expressions by Recursive Descent Theodore Norvell © 1999—2001. Access date September 14, 2006. Алгоритм преобразования инфиксной записи в обратную польскую нотацию Оригинальное описание алгоритма Расширение алгоритма для использования произвольного количества аргументов функции
Категория:Синтаксический анализ