Главная / ПрограммированиеСоздаём язык программирования → Лекция А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 priority[stack.last] >= priority[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. Написать калькулятор (стандартных) арифметических выражений.