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

Алгоритм сортировочной станции — способ разбора математических выражений, представленных в инфиксной нотации . Может быть использован для получения вывода в виде обратной польской нотации или в виде абстрактного синтаксического дерева . Алгоритм предложен Эдсгером Дейкстрой и назван им «алгоритм сортировочной станции», поскольку напоминает действие железнодорожной сортировочной станции .

Так же, как и вычисление значений выражений в обратной польской записи, алгоритм работает при помощи стека . Инфиксная запись математических выражений чаще всего используется людьми, её примеры: 2+4 и 3+6*(3-2). Для преобразования в обратную польскую нотацию используется 2 строки: входная и выходная, и стек для хранения операторов, ещё не добавленных в выходную очередь. При преобразовании алгоритм считывает 1 символ и производит действия, зависящие от данного символа.

Алгоритм

Пока не все токены обработаны:

Прочитать токен .
Если токен — число , то добавить его в очередь вывода.
Если токен — функция , то поместить его в стек.
Если токен — разделитель аргументов функции (например, запятая):

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

Если токен — оператор op1, то:

Пока присутствует на вершине стека токен оператор op2, чей приоритет выше или равен приоритету op1, и при равенстве приоритетов op1 является левоассоциативным :
- Переложить op2 из стека в выходную очередь;
Положить op1 в стек.

Если токен — открывающая скобка , то положить его в стек.
Если токен — закрывающая скобка :

Пока токен на вершине стека не открывающая скобка
- Переложить оператор из стека в выходную очередь.
- Если стек закончился до того, как был встречен токен открывающая скобка , то в выражении пропущена скобка.
Выкинуть открывающую скобку из стека, но не добавлять в очередь вывода.
Если токен на вершине стека — функция, переложить её в выходную очередь.

Если больше не осталось токенов на входе:

Пока есть токены операторы в стеке:

Если токен оператор на вершине стека — открывающая скобка , то в выражении пропущена скобка.
Переложить оператор из стека в выходную очередь.

Конец.

Каждый токен-число, функция или оператор выводится только один раз, а также каждый токен-функция, оператор или круглая скобка будет добавлен и удалён из стека по одному разу. Постоянное количество операций на токен, линейная сложность алгоритма O( n ).