Публикация Школы траблшутеров

Нетривиальный разбор обратной польской записи

Время чтения: 9 мин 35 сек
5 января 2024 г. Просмотров: 167

Алгоритмы, ЛогикаОлег Брагинский, Валерий Хлебнов

Появление электронных вычислителей совершило техническую революцию. Основатель «Школы траблшутеров» Олег Брагинский и ученик Валерий Хлебнов расскажут о методе перевода математических формул в вид удобный для решающих компьютерных устройств.

Обыватели недоумевают: почему разные вычислительные системы не могут дать единый ответ на детскую математическую задачку: «2 + 2 * 2»? Ответ кроется в применяемых алгоритмах. В умных устройствах для глупых пользователей механики решения сложных уравнений зашиты заранее.

Для использования примитивных арифмометров необходимо знать основы математики и теории алгоритмов. Важны последовательность вычислений и понимание приоритезации операторов. Скобки, степени, умножение и деление, а также вычитание растрачивают ценное мыслетопливо.

Красивое решение в 1920 году предложил польский логик Ян Лукасевич: перевёл классическую инфиксную запись «2 + 2 * 2» в постфиксную «2 2 * 2 +». Выражение предполагает расположение операторов после пары операнд. Упрощает поиск приоритета действий и разгадывание скобок.

Польская запись однозначно определяет порядок арифметических действий. Теперь становится понятна разница в решении вышеописанной детской задачи. Ответ будет зависеть от последовательности обработки действий: «2 2 + 2 *» равно восьми, а «2 2 * 2 +» даёт нам шесть.

Для наглядности разберём пример посложнее: увеличим количество действий, добавим степени и скобки. Чтобы не запутаться, не станем пугать читателей логарифмами, модулями, интегралами и прочими интересными инструментами царицы всех наук. Пытливые разберутся по аналогии.

До начала вычислений проведём предобработку выражения. Подготовительная работа поможет исключить ошибки вычислений на последующих этапах. Инфиксная запись понятна для общего восприятия, но не для проведения вычислений. Разберём выражение для наглядности.

При переводе в линейный вид замечаем необходимость использования дополнительных скобок для расстановки приоритета вычислений. Степени и корни главенствуют над умножением и делением. Те, в свою очередь, доминируют над сложением и вычитанием. Пишем слева-направо:

В случае с дробями фиксируем последовательно знаменатель за числителем. При написании обращаем внимание, что математическая «колбаса» прирастает не только с хвоста. Приоритезация последовательности действий вклинивает дополнительные скобки, забивает память компьютера:

Разложив приведённый пример по вагонам поезда чисел, соединённых математическими операторами и сгруппированных скобками, получим вектор из 60 позиций. Линейная запись программируется в любом языке, не смущая новичков засорённостью и громоздкостью:

Рассмотрим альтернативу для программистов, где для решения примера следуем правилам:

  • истинной является запись «операнд + операнд + оператор»
  • работаем чётко слева-направо для повышения важности применяем смещение влево:

Рассматриваемый метод позволяет избавиться от нагромождения скобок и от заботы о корректной последовательности вычислений. Запись использует меньшее количество знаков, несмотря на задействование дополнительных обозначений для возведения в степень и извлечения корней:

При трансформации у новичков возникает закономерный страх огрехов излишнего упрощения выражения. Ошибка в местоположении любого обозначения приводит к неминуемому провалу. Рекомендуем подбивать суммарное количество операндов и операторов для первичной проверки:

Разобрав пример до конца, удивляемся стройности записи в сравнении с классическим инфиксным подходом. Рассматриваемый метод демонстрирует достаточность 37 ячеек памяти для решения. Экономия вычислительных ресурсов в нашем случае составила более 38%. Но это ещё не всё:

Предлагаем рассмотреть два варианта решения получившегося выражения – обратной польской записи (ОПЗ): таблица – для системно-мыслящих; воронка – для визуалов и эстетов.

При первом прогоне схлопываем четвёрку в четвёртой степени, двойку в седьмой степени, умножаем семь на восемь, прибавляем двойку к семёрке, а также извлекаем кубический корень из восьмёрки. Ответы сносим под соответствующий оператор, удаляя использованные числа:

При втором подходе: пропускаем 256, вычисляем из 128 число 56, девять умножим на три, прибавим к двойке единицу. Количество решений в строке неумолимо сокращается, но не должно достигать нуля. Не позволяйте разношёрстности расстановки чисел и операторов ставить в ступор:

В третьей оптимизированной строке повторяем операцию: 72 поделим на восемь, а 27 разделим на тройку. Генерируется очередная закономерная последовательность неслучайно расставленных ячеек. Не обращаем внимание на образовавшиеся пустоты в таблице, мысленно стыкуем соседей:

В четвёртом цикле широко шагаем, складывая восьмёрку и 125, вычитая из 19 девятку. Ряды неумолимо редеют, приближая нас к неизбежному решению. У программистов может возникнуть ассоциация с архивацией и упаковкой данных разрозненных байт информации при бэкапах:

Пятый шаг нашего примера знаменуется единственным прыжком при вычислении 133 из 256. Последующие итерации занятной рекурсии будут состоять из единственных действий. Стоим на развилке: либо расчёты подходят к завершению, либо решаем пример уникальной сложности:

На шестом шаге таблица позволяет вычесть только 23 из 123. Оставшиеся действия недоступны на текущем этапе. Количество оставшихся операторов подсказывает сумму циклов до решения. В нашем случае осталось три («^», «/»,«^»). Записываем вычисления на новую линию:

В седьмой строке таблицы вычисляем сотню в квадрате, что означает перемножение её на себя же единожды. Получаем пока самое большое значение в матрице равное десяти тысячам. Запись ответов под знаками позволяет не запутаться какие значения сносим, а какие ячейки освобождаем:

Предпоследняя итерация предписывает разделить 10’000 на десятку. Буднично понижаем разрядность исходного числа, отбрасывая ноль. До получения конечного результата остаётся сделать один шаг. Не забываем снести полученное значение текущей строки под оператор:

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

Истинных записей на каждой итерации может быть не меньше, чем одна. На первых этапах их может быть множество, которое стремительно сокращается с каждым шагом цикла. Важно не перескакивать и не пропускать ячейки. Генерируем дополнительные источники ошибок:

Решение при помощи воронки упрощает понимание сжатия исходной строки, убивая пустые ячейки. Выравнивание слева добавляет порядок в визуальное оформление, демонстрирует экспоненциальное сокращение выражения на каждой ступени итераций рекурсии:

Вычисления легко поддаются кодировке: нашёл истинную запись «операнд + операнд + оператор» – реши, добежал до конца строки – примени рекурсию. В случае отсутствия конечного решения возвращаемся к проверке кодирования исходного выражения в ОПЗ, т.к. допустили ошибку.

Внимательные заметят, что решение практически не отличается от табличного. Описываем разными представлениями для большей понятности. Руководителям привычнее мыслить табличной формой, менеджеры чаще предпочитают наглядные графики и майнд-карты:

Проводя отсечение на каждом этапе, наблюдаем сокрушение математического колоса на глиняных ногах. Псевдослучайная последовательность значений в ячейках избавляется от громоздкой структуры. Решения находятся беглым взглядом, руки чешутся скорее записать очередную строку:

В нашем примере замечаем закономерность: вычисления производятся в первом блоке, состоящем из трёх ячеек. Уверяем, что подобное явление – частный случай рассматриваемой формулы, а не постоянное правило. Однако просматривается корреляция с решением слева-направо:

Уточним, что ОПЗ не приемлет в исходной записи отрицательных чисел. Рекомендуется заменять данные значения выражением [«0» «–» «число»], заполняя три ячейки памяти, или ввести оператор смены знака перед операндом. В нашем случае ячейки корней «-3» следует читать, как спецзнак:

Ещё одна интересная особенность ОПЗ заключается в вариативности написания без изменения конечного результата: строка «100 10 / 2 + 3 *» равнозначна выражению «3 2 100 10 / + *». Возможно только при выполнении правила: «От перемены мест слагаемых сумма не меняется»:

Ещё одним маркером проверки корректности исходного выражения является составное условие:

  • количество операндов превосходит сумму операций на единицу и
  • первая ячейка выражения всегда число, последняя – математическая операция.

Для окончательного понимания масштаба действий продемонстрируем сводную схему. Наблюдаем отсутствие незадействованных ячеек. Частные случаи решаемых выражений имеют уникальные рисунки. Полная схема воронки рассматриваемого примера будет выглядеть следующим образом:

ОПЗ сильно упростила компьютерные вычисления, высвободив значительное количество ресурсов для рационализации решения прикладных задач. Несмотря на постоянно растущие мощности ЭВМ, учёные до сих пор сталкиваются с ограничениями и ищут новые алгоритмы рационализации труда.