Functionally Solving Problems - Reverse Polish Notation Calculator
Reverse Polish Notation Calculator
1> string:tokens("10 4 3 + 2 * -", " "). ["10","4","3","+","2","*","-"]
Using the cons (|) operator in [Head|Tail] effectively behaves the same as pushing Head on top of a stack (Tail, in this case). Using a list for a stack will be good enough.--book
Erlang's list will represent our stack.
To read the expression, we just have to do the same as we did when solving the problem by hand. Read each value from the expression, if it's a number, put it on the stack. If it's a function, pop all the values it needs from the stack, then push the result back in. To generalize, all we need to do is go over the whole expression as a loop only once and accumulate the results. Sounds like the perfect job for a fold!--book
So the stack logic can be implemented via fold
We'll write the function responsible for all the looping and also the removal of spaces in the expression--book
-module(calc). -export([rpn/1]). rpn(L) when is_list(L) -> [Res] = lists:foldl(fun rpn/2, [], string:tokens(L, " ")), Res.
Alright what does this do?
rpn/1 takes a list and put it in a fold, (lists:foldl/3 a left fold to be precise). The three parameters are as follow:
First parameter (fun rpn/2): is a function that will apply to each element of the list.
Second parameter ([]): is an accumulator, something to store our computation for tail recursion.
Third parameter (string:tokens(L, "http://erldocs.com/R15B/stdlib/lists.html#foldl/3")): is the list we wish to fold.
Parsing the head of the stack.
rpn(X, Stack) -> [read(X)|Stack].
Converting the numbers in head value to either integer or float.
read(N) -> case string:to_float(N) of {error,no_float} -> list_to_integer(N); {F,_} -> F end.
Parsing the operators too.
rpn("+", [N1,N2|S]) -> [N2+N1|S]; rpn(X, Stack) -> [read(X)|Stack].
The rest of the operators...
rpn("+", [N1,N2|S]) -> [N2+N1|S]; rpn("-", [N1,N2|S]) -> [N2-N1|S]; rpn("*", [N1,N2|S]) -> [N2*N1|S]; rpn("/", [N1,N2|S]) -> [N2/N1|S]; rpn("^", [N1,N2|S]) -> [math:pow(N2,N1)|S]; rpn("ln", [N|S]) -> [math:log(N)|S]; rpn("log10", [N|S]) -> [math:log10(N)|S]; rpn(X, Stack) -> [read(X)|Stack].
rpn("sum",L) -> lists:sum(L);
Omg, I'm glad list have a sum function.
rpn("sum", Stack) -> [lists:sum(Stack)];
What I did wrong, I should have return a list, [], not just the value.
rpn("prod",L) -> [foldl(*,[],L)];
... stuck. I want to fold each and every item in the current list and apply the multiplication.
rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 1, Stack)];
No really what the flying hell?
Code Review, breaking it down for prod.
rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 1, Stack)];
Above is the original function.
Instead of fun erlang:'*'/2 can I replace it with * this?
Wait let me test if the book's code works first.
lists:foldl(*, 1, Stack) & lists:foldl('*', 1, Stack) does not work.
Time to look up the function fun erlang:'*'/2.
Online document doesn't show it... and the man page on unix doesn't come up with anything.
Assumption: fun erlang:'*'/2 is just an operator like -,+,/,etc....
Assuming that is true, let's try: fun erlang:'+'/2:
rpn("prod", Stack) -> [lists:foldl(fun erlang:'+'/2, 1, Stack)];
19> calc:rpn("10 10 20 0.5 prod"). 41.5
Oooooh it seems that my assumption is correct! Let's try - and /.
rpn("prod", Stack) -> [lists:foldl(fun erlang:'-'/2, 1, Stack)];
19> calc:rpn("10 10 20 0.5 prod"). 20.5 20> 10-10-20-0.5. -20.5 21> 0.5-20-10-10. -39.5
FML, the sign is different for -. Why...? Let's see / now before investigating that.
rpn("prod", Stack) -> [lists:foldl(fun erlang:'/'/2, 1, Stack)];
19> calc:rpn("10 10 20 0.5 prod"). 40 20> 10/10/20/0.5. 0.1
Fml. The orders in - & / matters compare to + & * perhaps that is why the answers is funky.
Why is the second parameter in prod is 1 instead of []?
Let's try: rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, [], Stack)];.
Let's try: rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 0, Stack)];.
Let's try: rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 2, Stack)];.
HMMM... the accumulator eh.
rpn("prod", Stack) -> [lists:foldl(fun erlang:'/'/2, H, [H|T])];
FML. Doesn't work, the H,T are unbounded.