на список элементов:
>["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