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