> For the complete documentation index, see [llms.txt](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/23.-dinamicheskie-struktury-dannykh.-algoritm-deikstry-dlya-perevoda-iz-infiksnoi-v-obratnuyu-polsku.md). # 23. Динамические структуры данных. Алгоритм Дейкстры для перевода из инфиксной в обратную польскую запись. **Динамические структуры данных** - составные структуры данных, динамически меняющие свой размер во время выполнения программы. ## Итератор **Итераторы** - это обобщение указателей, которые позволяют программе работать с различными структурами данных единообразно. Вместо работы с опредленными типами данных алгоритмы работают с диапазоном значений, заданным типом итератора. Алгоритмы могут работать с любой структурой данных, удовлетворяющей требованиям итератора. ```c struct Iterator { Node* current; }; ``` ## Польская нотация (запись) Классическая форма записи: • a + b • 2 + 3 \* (1 / 5 - 4) • sin(3 \* 5 - 1 ) ^ 2 + 8 Обратная польская нотация: • a b + • 2 3 1 5 / 4 - \* + • 3 5 \* 1 - sin 2 ^ 8 + :star:[Онлайн-калькулятор](http://primat.org/news/obratnaja_polskaja_zapis/2016-04-09-1181), в котором можно перевти из польской в инфиксную и обратно. ## Алгоритм Дейкстры Пока в выражении есть лексемы: 1. Берем очередную лексему 2. Если лексема - операнд, добавляем в выходную строку 3. Если лексема является функцией, помещаем ее в стек 4. Если оператор и его приоритет меньше, либо равен приоритету оператора, находящегося на вершине стека, выталкиваем верхние операторы из стека в выходную строку до тех пор, пока не встретится оператор с меньшим приоритетом, или открывающая круглая скобка, или стек станет пустым, и помещаем его в стек.