Зима - самая холодная пора года, но даже она не настолько холодна, как реакция интервьювера на твою реализацию калькулятора для постфиксной нотации. Тем не менее у нас нет времени на эмоции, поэтому приступим к разбору алгоритма сортировочной станции, упомянутого в предыдущем посте.

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

Начнём с самых простых примеров: применение бинарного оператора к операндам. Например, для выражение 2 + 3 аналогичным выражением в постфиксной нотации будет 2 3 +. То же будет верно для других бинарных операторов. Попробуем составить простую модель на C# для работы с такими выражениями:

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

Всё это работает великолепно до того момента, пока мы не захотим усложнить исходное выражение и добавить ещё один оператор 2 + 3 - 4. В данном случае аналогичным постфиксным выражением будет 2 3 + 4 -. Заметим, что предыдущий алгоритм не может сохранять больше одного оператора во временном хранилище, таким образом мы потеряем один оператор в процессе вычисления и в результате получим 2 3 4 -. Это не может не огорчать, поэтому попробуем внести улучшение в наш алгоритм преобразования.

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

Красота! Но что же делать, если операторы имеют разный приоритет? 2 + 3 * 4 выражение должно быть преобразовано к выражению 2 3 4 * +, но никак не к выражению 2 3 + 4 *. Для дальнейшего улучшения алгоритма рассмотрим также выражение 2 * 3 + 4 и его аналог 2 3 * 4 +. Отсюда мы можем сделать вывод, что наш алгоритм не работает только для случаев, когда следующий оператор имеет более высокий приоритет, чем предыдущий. Причём в случае, когда следующий оператор имеет более высокий приоритет, операторы должны как бы поменяться местами в результирующем выражении. Отсюда напрашивается вывод, что необходимо для хранилища операторов использовать стек, внесём очередное изменение в наш алгоритм:

• Пока выражение имеет токены берём очередной токен:
  • Если токен является операндом, то записываем его в результирующую последовательность;
  • Если токен является оператором, то запоминаем его в отдельном хранилище. Если хранилище содержит другой оператор, то записываем сохранённый оператор в результирующую последовательность, а новый оператор сохраняем в хранилище.
  • Если токен является оператором, то:
    • Пока стек операторов не пустой, и в вершине стека лежит оператор с не меньшим (>=) приоритетом, достаём его из стека и записываем в результирующую последовательность;
    • Сохраняем токен в стек операторов.
• Достаём сохранённый токен из хранилища и добавляем его сохраненные операторы из стека операторов и добавляем их в результирующее выражение.

Остался последний штрих - добавить подержку скобок, которые могут менять приоритет выполнения операций. Рассмотрим следующее выражение (2 + 3 * 4) / 5 и аналогичное выражение в постфиксной нотации 2 3 4 * + 5 /. Другими словами, выражение в скобках должно быть расчитано перед выполнением деления. Расшририм список возможных операторов скобочными операторами порядка:

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

• Пока выражение имеет токены берём очередной токен:

  • Если токен является операндом, то записываем его в результирующую последовательность;

  • Если токен является оператором вычисления (не скобочным), то :

    • Пока стек операторов не пустой, и в вершине стека лежит оператор с не меньшим (>=) приоритетом, достаём его из стека и записываем в результирующую последовательность;
    • Сохраняем токен в стек операторов.

  • Если токен является открывающайся скобкой, то сохраняем оператор в стек операторов;

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

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

Полную реализацию можно посмотреть на GitHub проекта coding-interview. На этом будем заканчивать разбор алгоритма сортировочной станции, и, не теряя времени, переходим к алгоритму токенизации, описанному в следующем посте.