Алгоритм сортировочной станции Дейкстры получил название в честь железнодорожной сортировочной станции - и работает очень похоже.
Он преобразует обычную инфиксную запись:
3 + 4 * 2
в постфиксную:
3 4 2 * +
После этого калькулятору уже не нужно каждый раз разбираться с приоритетами операторов и строить полноценное AST.
Как работает идея:
- один стек хранит операторы;
- второй поток формирует результат;
- операторы с более высоким приоритетом выходят раньше;
- скобки и ассоциативность обрабатываются по правилам стека.
В итоге выражение можно вычислять последовательно и без рекурсивного спуска.
Простой, старый и до сих пор очень красивый алгоритм для парсеров, калькуляторов и компиляторов.
#Algorithms #C #Programming #Compilers #ComputerScience
Он преобразует обычную инфиксную запись:
3 + 4 * 2
в постфиксную:
3 4 2 * +
После этого калькулятору уже не нужно каждый раз разбираться с приоритетами операторов и строить полноценное AST.
Как работает идея:
- один стек хранит операторы;
- второй поток формирует результат;
- операторы с более высоким приоритетом выходят раньше;
- скобки и ассоциативность обрабатываются по правилам стека.
В итоге выражение можно вычислять последовательно и без рекурсивного спуска.
Простой, старый и до сих пор очень красивый алгоритм для парсеров, калькуляторов и компиляторов.
#Algorithms #C #Programming #Compilers #ComputerScience