Изучай Haskell во имя добра!

Мы уложились в четыре образца. Образцы будут сопоставляться транслятором в порядке записи. Вначале функция свёртки проверит, равен ли текущий элемент "*". Если да, то функция возьмёт список, например [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] – это число мы вернём.

Погоняем нашу функцию:

ghci> solveRPN "10 4 3 + 2 * -"

-4.0

ghci> solveRPN "2 3.5 +"

5.5

ghci> solveRPN "90 34 12 33 55 66 + * - +"

-3947.0

ghci> solveRPN "90 34 12 33 55 66 + * - + -"

4037.0

ghci> solveRPN "90 3.8 -"

86.2

Отлично, работает!

Добавление новых операторов

Чем ещё хороша наша функция – её можно легко модифицировать для поддержки других операторов. Операторы не обязательно должны быть бинарными. Например, мы можем создать оператор log, который выталкивает из стека одно число и заталкивает обратно его логарифм. Также можно создать тернарный оператор, который будет извлекать из стека три числа и помещать обратно результат. Или, к примеру, реализовать оператор sum, который будет поднимать все числа из стека и суммировать их.

Давайте изменим нашу функцию так, чтобы она понимала ещё несколько операторов.

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 (x:y:ys) "/" = (y / x):ys

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

      foldingFunction (x:xs) "ln" = log x:xs

      foldingFunction xs "sum" = [sum xs]

      foldingFunction xs numberString = read numberString:xs

Прекрасно. Здесь / – это, конечно же, деление, и ** – возведение в степень для действительных чисел. Для логарифма мы осуществляем сравнение с образцом для одного элемента и «хвоста» стека, потому что нам нужен только один элемент для вычисления натурального логарифма. Для оператора суммы возвращаем стек из одного элемента, который равен сумме элементов, находившихся в стеке до этого.

ghci> solveRPN "2.7 ln"

0.9932517730102834

ghci> solveRPN "10 10 10 10 sum 4 /"

10.0

ghci> solveRPN "10 10 10 10 10 sum 4 /"

12.5

ghci> solveRPN "10 2 ^"

100.0

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