Просто ли написать «калькулятор»?

Какой «формальный язык» является самым простым, но всё же практически полезным?

Конечно, «язык» арифметических выражений.

В стандартных дистрибутивах linux-систем есть консольная утилита bc, позволяющая вычислять арифметические выражения (с соблюдением обычных правил приоритета операций):

$ bc
[...]
2 + 2 * 2
6
(2 + 2) * 2
8

На вид ничего сложного, но как это вообще работает?

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

Конечно, обязательно кто-то захочет блеснуть остроумием и предложит что-то вроде этого (пример на Ruby, но во всех интерпретируемых языках можно написать подобное):

input = STDIN.gets
# eval выполняет любой Ruby-код, переданный в строке
puts eval(input)

Над шуткой мы посмеёмся, но если серьёзно, то, конечно, наш курс как раз про то, как реализовать эту функцию eval, предполагая, что за нас её не написали :)

Если читатель (конечно, не знающий ответа наперёд) мысленно предложит в итоге некий работающий алгоритм, то можно только воскликнуть — «Далеко пойдёт!» :)

Обратная польская запись

Недолго поломав голову над предложенной задачей, временно её отложим и возьмём упрощённую задачу.

Вся проблема с нашими арифметическими выражениями в том, что надо разбираться с:

• приоритетом операций (сначала умножать, потом складывать)
• скобками (сначала выполнять то, что в скобках)

А что, если бы существовала возможность записать произвольное арифметическое выражение без этих затрудняющих программную обработку элементов?

Такой способ есть — называется «обратная польская запись» («reverse Polish notation», RPN).

В традиционной форме записи знаки операций стоят между операндами (числами), поэтому такая запись называется «инфиксной»:

2 + 2

В RPN знак операции ставится после операндов (поэтому она ещё называется «постфиксной»):

2 2 +

Фишка в том, что в RPN нет скобок и приоритета операций (и они не нужны). Например, выражение 2 + 2 * 2 будет записано вот как:

2 2 2 * +

Для его вычисления надо сделать вот что:

1. Идти слева направо, пока не встретим знак операции
2. Переписать сам знак и ближайшую к нему слева пару чисел на результат применения этой операции к этим числам (левое число является первым операндом операции, правое вторым)
3. Продолжить-повторить с текущего места двигаться вправо, пока выражение не будет разобрано полностью

В качестве единственного числа «на ленте» останется результат всех вычислений.

Посмотрим, как этот алгоритм работает с вышеуказанным выражением.

Запишем результат каждого «такта» работы нашей «вычислительной машины» (по алгоритму выше) с новой строки (символом v обозначен «курсор»):

v
2 2 2 * +

  v
2 2 2 * +

    v
2 2 2 * +

      v
2 2 2 * +

  v
2 4 +

    v
2 4 +

v
6

Инфиксное выражение (2 + 2) * 2 в RPN будет выглядеть вот как:

2 2 + 2 *

Читателю стоит мысленно вычислить его результат, убедившись, что вышеприведённый алгоритм работает.

RPN-машина

Пора перейти к практике — к написанию кода.

Реализуем калькулятор, который бы мог вычислять выражения, записанные в RPN (для начала реализуем только операции сложения и умножения).

Перед тем, как приступить к коду, учтём вот какой момент.

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

Стековый автомат также называют «pushdown automaton», «магазинный автомат», «автомат с магазинной памятью».

Одной из таких полезных абстракций является так называемый «стековый автомат».

Напомним, что стек — это структура данных, работающая по принципу «последний зашёл, первый вышел». В Ruby стек моделируется (имитируется) с помощью методов массива #push и #pop:

stack = []

stack.push 1
stack.push 2
stack.push 3

# stack == [1, 2, 3]

stack.pop # 3
stack.pop # 2
stack.pop # 1

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

Стековый автомат. Справа стек, снизу входная лента (на которой записано, в нашем случае, обрабатываемое выражение), сверху блок управления. (Иллюстрация с Вики.)

Реализуем «виртуальный стековый автомат» по вычислению RPN-выражений следующим образом:

• входное выражение записано по элементам (числа, операции) в массив, моделирующий «входную ленту» автомата;
• внутренняя память моделируется массивом с методами #push и #pop, как показано выше;
• управляющий блок моделируется циклом, пробегающим по всем элементом «ленты».

Получится вот такая заготовка:

stack = []
input = [2, 2, 2, '*', '+']

input.each do |op|
  # здесь основной код
  # ...
end

Алгоритм вычислений RPN-выражения весьма простой (во всех примерах мы не рассматриваем, для простоты, обработку ошибок — в разработке реальных интерпретаторов и компиляторов это отдельная сложная тема):

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

Бесхитростная и буквальная реализация на Ruby получается вот такая:

stack = []
input = [2, 2, 2, '*', '+']

input.each do |op|
  case op
  when '*', '+'
    number2 = stack.pop
    number1 = stack.pop

    result =
      case op
      when '*'
        number1 * number2
      when '+'
        number1 + number2
      # обработка других операторов
      # ...
      end

    stack.push result
  else
    stack.push op
  end
end

puts stack.pop

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

На самом деле, если что и как делает данная программа на 25 строк стало понятным, о всём остальном можно не беспокоиться :)

Упражнение 1. Написать калькулятор, который бы просил пользователя ввести выражение в RPN и выводил бы результат его вычисления.