Алгоритм сортировочной станции Дейкстры получил название в честь железнодорожной сортировочной станции - и работает очень похоже.

Он преобразует обычную инфиксную запись:

3 + 4 * 2

в постфиксную:

3 4 2 * +

После этого калькулятору уже не нужно каждый раз разбираться с приоритетами операторов и строить полноценное AST.

Как работает идея:

- один стек хранит операторы;
- второй поток формирует результат;
- операторы с более высоким приоритетом выходят раньше;
- скобки и ассоциативность обрабатываются по правилам стека.

В итоге выражение можно вычислять последовательно и без рекурсивного спуска.

Простой, старый и до сих пор очень красивый алгоритм для парсеров, калькуляторов и компиляторов.

#Algorithms #C #Programming #Compilers #ComputerScience