😠23. Динамические структуры данных. Алгоритм Дейкстры для перевода из инфиксной в обратную польскую

запись.

Динамические структуры данных - составные структуры данных, динамически меняющие свой размер во время выполнения программы.

Итератор

Итераторы - это обобщение указателей, которые позволяют программе работать с различными структурами данных единообразно. Вместо работы с опредленными типами данных алгоритмы работают с диапазоном значений, заданным типом итератора. Алгоритмы могут работать с любой структурой данных, удовлетворяющей требованиям итератора.

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 +

⭐Онлайн-калькулятор, в котором можно перевти из польской в инфиксную и обратно.

Алгоритм Дейкстры

Пока в выражении есть лексемы:

1. Берем очередную лексему

2. Если лексема - операнд, добавляем в выходную строку

3. Если лексема является функцией, помещаем ее в стек

4. Если оператор и его приоритет меньше, либо равен приоритету оператора, находящегося на вершине стека, выталкиваем верхние операторы из стека в выходную строку до тех пор, пока не встретится оператор с меньшим приоритетом, или открывающая круглая скобка, или стек станет пустым, и помещаем его в стек.