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

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

Ещё одна вещь, о которой стоит подумать: а как мы будем реализовывать стек? Я предлагаю использовать список. Также рекомендую в качестве вершины стека использовать «голову» списка – потому что добавление элемента к «голове» (началу) списка работает гораздо быстрее, чем добавление элемента к концу списка. В таком случае, если у нас, например, есть стек 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

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

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

foldingFunction xs numberString = read numberString:xs

Мы уложились в четыре образца. Образцы будут сопоставляться транслятором в порядке записи. Вначале функция свёртки проверит, равен ли текущий элемент "*". Если да, то функция возьмёт список, например [3,4,9,3], и присвоит двум первым элементам имена xи yсоответственно. В нашем случае xбудет соответствовать тройке, а y– четвёрке; ysбудет равно [9,3]. В результате будет возвращён список, состоящий из [9,3], и в качестве первого элемента будет добавлено произведение тройки и четвёрки. Таким образом, мы выталкиваем два первых числа из стека, перемножаем их и помещаем результат обратно в стек. Если элемент не равен "*", сопоставление с образцом продолжается со следующего элемента, проверяя "+", и т. д.

Если элемент не совпадёт ни с одним оператором, то мы предполагаем, что это строка, содержащая число. Если это так, то мы вызываем функцию readс этой строкой, чтобы получить число, добавляем его в вершину предыдущего стека и возвращаем получившийся стек.

Для списка ["2","3","+"]наша функция начнёт свёртку с самого левого элемента. Стек в начале пуст, то есть представляет собой []. Функция свёртки будет вызвана с пустым списком в качестве стека (аккумулятора) и "2"в качестве элемента. Так как этот элемент не является оператором, он будет просто добавлен в начало стека []. Новый стек будет равен [2], функция свёртки будет вызвана со значением [2]в качестве стека и "3"в качестве элемента; функция вернёт новый стек, [3,2]. Затем функция свёртки вызывается в третий раз, со стеком равным [3,2]и элементом "+". Это приводит к тому, что оба числа будут вытолкнуты из стека, сложены, а результат будет помещён обратно в стек. Результирующий стек равен [5]– это число мы вернём.