Postfix notation, also known as reverse Polish notation, has operators come after their operands in mathematical expressions. It has no need for operator precedence or parentheses to specify evaluation order.

Evaluation is typically done using a stack. Numbers are pushed onto the stack, and operators pop out numbers and pushes back the result. The State monad would be useful for maintaining such a stack.

There may be errors with some expressions. For example, an expression may be ill-formed, or there may be a division by zero. It would be useful to use the Maybe monad so that we can return Nothing if there is an error.

Finally for this problem, we would like to keep track of changes to the stack and which operators are applied to which numbers. The function should also return a list, with each entry showing the state of the stack after an operand has been pushed or an operator has been applied. Logging each entry can be done with the Writer monad.

Unfortunately, it would be very cumbersome to use these monads directly together. Monad transformers are a way to make it substantially easier to use more than one monad at the same time. Use monad transformers to compose the State, Maybe, and Writer monads into a single monad to implement a function which evaluates an expression in postfix notation. It should also return the history of the calculation.

Examples

The result of applying subtraction to 8 and 5 should be 3:

>>> fst $ calculatePostfix [Operand 8, Operand 5, Operator Subtract]
Just 3

It should be an error if no operator is applied to two or more numbers:

>>> fst $ calculatePostfix [Operand 8, Operand 6]
Nothing

Negation applies to a single number:

>>> fst $ calculatePostfix [Operand 8, Operator Negate]
Just (-8)

But it is an error if there is only one number for a binary operator:

>>> fst $ calculatePostfix [Operand 8, Operator Add]
Nothing

The parsePostfix function can be used to conveniently create an expression:

>>> fst $ calculatePostfix $ parsePostfix "8 5 4 10 + - 3 * negate +"
Just 35

The second element in the return value should show the history of the calculation:

>>> mapM_ print $ snd $ calculatePostfix $ parsePostfix "8 5 4 10 + - 3 * negate +"
([8],Nothing)
([5,8],Nothing)
([4,5,8],Nothing)
([10,4,5,8],Nothing)
([14,5,8],Just Add)
([-9,8],Just Subtract)
([3,-9,8],Nothing)
([-27,8],Just Multiply)
([27,8],Just Negate)
([35],Just Add)

Even if the expression is invalid, the second element should still show the history of the calculation until the point at which there is an error:

>>> fst $ calculatePostfix $ parsePostfix "1 2 * +"
Nothing
>>> mapM_ print $ snd $ calculatePostfix $ parsePostfix "1 2 * +"
([1],Nothing)
([2,1],Nothing)
([2],Just Multiply)

Hint

A single element within a mathematical expression. A list of these elements comprises an expression in postfix notation.

Encodes an operator for a mathematical expression.

Parses a string containing a mathematical expression in postfix notation. This can make it easier to write down an expression in a more conventional form.

For example,

>>> parsePostfix "3 4 2 - *"
[Operand 3,Operand 4,Operand 2,Operator Subtract,Operator Multiply]

The operators are encoded as follows: