Алгоритм Дейкстры (Сортировочная станция)

Модуль "Выражения" • урок 5 из 7 • ~12 минут

Алгоритм Дейкстры (Сортировочная станция): откуда имя

Название алгоритма Shunting-yard algorithm произошло из-за его схожести с железнодорожным узлом:

• Операнды (числа) - это обычные вагоны, они всегда едут прямо на "выходной путь".
• Операторы (+, -, *, /) - это локомотивы. Они временно загоняются в тупик ("Стек операторов"), пока не придет их очередь двигаться на выход в соответствии с приоритетом.

Правила работы алгоритма

Для работы требуется выходная очередь (массив ответа) и стек для хранения операторов. Читаем строку посимвольно слева направо:

1. Если токен - число или переменная, он сразу добавляется в выходную очередь.
2. Если токен - открывающая скобка (, она помещается в стек операторов.
3. Если токен - закрывающая скобка ), операторы выталкиваются из стека в выход до тех пор, пока на вершине не покажется открывающая скобка. Сами скобки уничтожаются.
4. Если токен - оператор (+, -, *, /):
   • Пока на вершине стека находится оператор с большим или равным приоритетом, выталкиваем его из стека в выходную очередь.
   • Затем помещаем текущий оператор в стек.
5. В конце строки все оставшиеся в стеке операторы выталкиваются в выход.

Как вычислить ОПЗ?

Главная прелесть Обратной польской записи в том, что для ее вычисления больше не нужны ни скобки, ни приоритеты. Машина может вычислить все за один проход, используя простейший стек операндов.

Правила вычисления ОПЗ (чтение слева направо):

• Если число - кладем в стек.
• Если операция - достаем из стека два последних числа, применяем к ним операцию и результат кладем обратно в стек.

Алгоритм Дейкстры в коде на языке Си

Ядро алгоритма Дейкстры - это обработчик прихода нового оператора. Цикл `while` реализует логику вытеснения операторов на основе их приоритета.

// Функция приоритета
int priority(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0; // Для скобок и неизвестных символов
}

// Приход нового оператора из входной строки
void process_operator(char current_op, Stack* operator_stack, Queue* output) {
    while (!is_empty(operator_stack)) {
        char top_op = top(operator_stack);
        
        // Если на вершине стека оператор с большим или равным приоритетом
        if (priority(top_op) >= priority(current_op)) {
            enqueue(output, pop(operator_stack)); // Выталкиваем его в ответ
        } else {
            break; // Вершина слабее, останавливаемся
        }
    }
    // Кладем пришедший оператор в стек
    push(operator_stack, current_op);
}