Миран Липовача - Изучай Haskell во имя добра!

Обычно мы записываем математические выражения в инфиксной нотации, например: 10 – (4 + 3) * 2. Здесь +, *и –представляют собой инфиксные операторы, такие же, как инфиксные функции Haskell ( +, `elem`и т. д.). Так нам удобнее, потому что мы можем легко разобрать подобную формулу в уме. Но у такой записи есть и негативное свойство: приходится использовать скобки для обозначения приоритета операций.

Обратная польская запись (ОПЗ) является одним из способов записи математических выражений. В ОПЗ операторы записываются не между числами, а после них. Так, вместо 4 + 3 нужно писать 4 3 +. Но как тогда записать выражения, содержащие несколько операторов? Например, как бы мы записали выражение, складывающее 4 и 3, а потом умножающее сумму на 10? Легко: 4 3 + 10 *. Поскольку 4 3 + равно 7, то всё выражение равно 7 10 *, т. е. 70. Поначалу такая запись воспринимается с трудом, но её довольно просто понять и использовать, так как необходимости в скобках нет и произвести вычисление очень легко. Хотя большинство современных калькуляторов используют инфиксную нотацию, некоторые люди до сих пор являются приверженцами калькуляторов, использующих ОПЗ.

Как мы можем вычислить результат? Представьте себе стек. Вы проходите по выражению слева направо. Если текущий элемент – число, его надо поместить ( push – «втолкнуть») в стек. Если мы рассматриваем оператор, необходимо взять ( pop – «вытолкнуть») два числа с вершины стека, применить к ним оператор и втолкнуть результат обратно в стек. Когда вы достигнете конца выражения, у вас должно остаться одно число, если, конечно, выражение было записано правильно. Это число и будет результатом.

Давайте разберём выражение 10 4 3 + 2 * –. Сначала мы помещаем 10 в стек; в стеке теперь содержится одно число. Следующий элемент – число 4, которое мы также помещаем в стек. То же проделываем со следующей тройкой – стек теперь содержит 10, 4, 3. И наконец-то нам встречается оператор, а именно «плюс». Мы выталкиваем предыдущие два числа из стека (в стеке остаётся 10), складываем их, помещаем результат в стек. Теперь в стеке 10, 7. Заталкиваем 2 в стек, теперь там 10, 7, 2. Мы снова дошли до оператора; вытолкнем 7 и 2 из стека, перемножим их, положим результат в стек. Умножение 7 на 2 даст 14; в стеке будет 10, 14. Получаем последний оператор – «минус». Выталкиваем 10 и 14 из стека, вычитаем 10 из 14, получаем –4, помещаем число в стек, и так как у нас больше нет чисел и операторов для разбора, мы получили конечный результат!

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

Наша функция будет принимать строку, содержащую выражение в обратной польской записи, например, "10 4 3 + 2 * -", и возвращать нам результат вычисления этого выражения.

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

solveRPN :: String –> Double

ПРИМЕЧАНИЕ.В процессе работы очень полезно сначала подумать о том, какой будет декларация типа функции, и записать её, прежде чем приступать к её реализации. В языке Haskell декларация типа функции говорит нам очень многое о функции благодаря строгой системе типов.

Отлично. При реализации решения проблемы на языке Haskell хорошо припомнить, как вы делали это вручную, и попытаться выделить какую-то идею. В нашем случае мы видим, что каждое число и оператор рассматривались как отдельные элементы. Так что будет полезно разбить строку вида "10 4 3 + 2 * –"на список элементов:

["10","4","3","+","2","*","–"]

Идём дальше. Что мы мысленно делали со списком элементов? Мы проходили по нему слева направо и работали со стеком по мере прохождения списка. Последнее предложение ничего не напоминает? Помните, в главе, посвящённой свёрткам, мы говорили, что практически любая функция, которая проходит список слева направо или справа налево, один элемент за другим, и накапливает (аккумулирует) некоторый результат – неважно, число, список или стек, – может быть реализована в виде свёртки?