Просто ли написать «калькулятор»?
Какой «формальный язык» является самым простым, но всё же практически полезным?
Конечно, «язык» арифметических выражений.
В стандартных дистрибутивах 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 * +
Для его вычисления надо сделать вот что:
- Идти слева направо, пока не встретим знак операции
- Переписать сам знак и ближайшую к нему слева пару чисел на результат применения этой операции к этим числам (левое число является первым операндом операции, правое вторым)
- Продолжить-повторить с текущего места двигаться вправо, пока выражение не будет разобрано полностью
В качестве единственного числа «на ленте» останется результат всех вычислений.
Посмотрим, как этот алгоритм работает с вышеуказанным выражением.
Запишем результат каждого «такта» работы нашей «вычислительной машины» (по алгоритму выше) с новой строки (символом 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-выражения весьма простой (во всех примерах мы не рассматриваем, для простоты, обработку ошибок — в разработке реальных интерпретаторов и компиляторов это отдельная сложная тема):
- Рассмотреть очередной элемент с ленты
- Если этот символ — операция, то вытащить из стека два элемента, провести над ними данную операцию, закинуть результат в стек
- Иначе (т.е. если этот символ — число) — закинуть данный элемент в стек
- Перейти к следующему элементу
- (Когда просмотрели всю ленту:) Вывести верхний элемент стека
Бесхитростная и буквальная реализация на 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 и выводил бы результат его вычисления.