Главная / ПрограммированиеСоздаём язык программирования → Лекция А2. Алгоритм сортировочной горки

Парсинг инфиксиных выражений

Знаете ведь известный анекдот ведь про то, как математик отвечает на вопрос «как вскипятить воду в чайнике»?

Спрашивают математика и физика, как вскипятить воду при помощи электрического чайника.

Оба отвечают примерно так:

• налить воду;
• включить в розетку;
• нажать кнопку питания;
• дождаться, пока закипит;
• готово.

Следующий вопрос задают такой: а как вскипятить воду, если в чайник уже налита вода?

Физик: «Ну, включить в розетку, нажать кнопку питания и так далее..»

Математик (на секунду задумавшись): «Вылить воду, тем самым сведя задачу к предыдущему случаю.

Предположим, что у нас был бы алгоритм, который позволяет из инфиксной записи выражения получить RPN… Тогда бы «задача свелась к предыдущей».

И алгоритм такой есть! Придумал и описал в 1961г. его Э. Дейкстра.

Называется алгоритм метафорически-образно «сортировочная горка».

Shunting yard

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

Сортировочная горка

Алгоритм Дейкстры работает на уже известном нам «стековом автомате». Нам понадобится использовать «входную ленту», «стек» (называемый в случае данного алгоритма «стек операторов»), «выходную ленту»:

# Входное выражение 1 + 2 * (3 + 4)
# На выходе хотим получить 1 2 3 4 + * +
input = [1, '+', 2, '*', '(', 3, '+', 4, ')']

stack = []

output = []

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

В общем виде, без избыточных деталей, алгоритм вот какой:

  1. Рассмотреть очередной элемент с входной ленты:
    • Если это число, то записать на выходную ленту
    • Если это левая скобка (, то закинуть её в стек операторов
    • Если это оператор:
      1. Вытеснить по одному все операторы, у которых приоритет ≥ рассматриваемого, из стека на выходную ленту (приоритет умножение и деления больше приоритета сложения и вычитания)
      2. Закинуть рассматриваемый оператор в стек
    • Если это правая скобка ):
      1. Вытеснить по одному все операторы из стека на выходную ленту, пока не встретим левую скобку (.
      2. Данную левую скобку из стека просто отбросить, рассматриваемую правую тоже.
  2. Перейти к следующему элементу.
  3. (Когда просмотрели всю входную ленту:) Вытеснить по одному все операторы, оставшиеся в стеке, на выходную ленту.

А причём тут сортировочная горка?

Давайте на примере.

Представим, что у нас двигаются «вагончики» (каждый символ — число или оператор — сидит в отдельном вагончике) справа налево.

Справа — входная лента.

Слева — выходная.

Снизу — «вспомогательный путь», стек операторов.

И вот как работает вышеприведённый алгоритм, преобразуя инфиксиное выражение 1 + 2 * (3 + 4) в постфиксное 1 2 3 4 + * +.

Мотивация «вагончиков» такая («алгоритм сортировочной горки» другими словами):

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

Напишем код:

# Входное выражение 1 + 2 * (3 + 4)
# На выходе хотим получить 1 2 3 4 + * +

input = [1, '+', 2, '*', '(', 3, '+', 4, ')']
stack = []
output = []

# Приоритет операций
priorities = {'+' => 1, '-' => 1, '*' => 2, '/' => 2}

# Рассмотреть каждый символ входной ленты
input.each do |token|
  case token
  # Если этот символ - число, то сразу отправить на выходную ленту
  when Numeric
    output.push token

  # Если открывающая скобка - сразу закинуть в стек
  when '('
    stack.push token

  # Если оператор
  when '+', '-', '*', '/'
    # Пока сверху стека какой-то оператор И этот оператор с таким же или меньше приоритетом
    while priorities[stack.last] && priorities[stack.last] >= priorities[token]
      # отправить оператор из стека на выходную ленту
      output << stack.pop
    end

    # Закинуть рассматриваемый оператор в стек
    stack.push token

  # Если закрывающая скобка
  when ')'
    # Пока сверху стека не открывающая скобка
    while stack.last != '('
      # отправить оператор со стека на выходную ленту
      output << stack.pop
    end

    # Убрать из стека найденную открывающую скобку
    stack.pop
  end
end

# Перенести все операторы из стека на выходную ленту
# Пока стек не пустой
until stack.empty?
  # перенести символ сверху стека на выходную ленту
  output << stack.pop
end

# Вывести результат
puts output.inspect

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

Упражнение 2. Написать калькулятор (стандартных) арифметических выражений.