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

Обратная польская запись (ОПЗ) является одним из способов записи математических выражений. В ОПЗ операторы записываются не между числами, а после них. Так, вместо 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","*","–"]

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

В нашем случае будем использовать левую свёртку, поскольку мы проходим список слева направо. Аккумулятором будет стек, и, следовательно, результатом свёртки также будет стек, но, как мы видели, он будет содержать единственный элемент.

Ещё одна вещь, о которой стоит подумать: а как мы будем реализовывать стек? Я предлагаю использовать список. Также рекомендую в качестве вершины стека использовать «голову» списка – потому что добавление элемента к «голове» (началу) списка работает гораздо быстрее, чем добавление элемента к концу списка. В таком случае, если у нас, например, есть стек 10, 4, 3, мы представим его списком [3,4,10].

Теперь мы знаем достаточно для того, чтобы написать черновик функции. Она будет принимать строку, например "10 4 3 + 2 * –", разбивать её на элементы и формировать из них список, используя функцию words. Получится ["10","4","3","+","2","*","–"]. Далее мы выполним левую свёртку и в конце получим стек, содержащий единственный элемент, [–4]. Мы получим этот элемент из списка; он и будет окончательным результатом.

Вот черновик нашей функции:

solveRPN :: String –> Double

solveRPN expr = head (foldl foldingFunction [] (words expr))

where foldingFunction stack item = ...

Мы принимаем выражение и превращаем его в список элементов. Затем выполняем свёртку, используя некоторую функцию. Обратите внимание на []: это начальное значение аккумулятора. Аккумулятором будет стек – следовательно, []представляет пустой стек, каковым он и должен быть в самом начале. После получения результирующего списка с единственным элементом мы вызываем функцию headдля получения первого элемента.

Всё, что осталось, – реализовать функцию для свёртки, которая будет принимать стек, например [4,10], элемент, например "3", и возвращать новый стек, [3,4,10]. Если стек содержит [4,10], а элемент равен *, то функция должна вернуть [40]. Но прежде всего давайте перепишем функцию в бесточечном стиле, так как она содержит множество скобок: лично меня они бесят!

solveRPN :: String –> Double

solveRPN = head . foldl foldingFunction [] . words

where foldingFunction stack item = ...

То-то! Намного лучше. Итак, функция для свёртки принимает стек и элемент и возвращает новый стек. Мы будем использовать сопоставление с образцом для того, чтобы получать первые элементы стека, и для сопоставления с операторами, например *и –.

solveRPN :: String –> Double

solveRPN = head . foldl foldingFunction [] . words

where

foldingFunction (x:y:ys) "*" = (x * y):ys