Copyright | Copyright (C) 2022 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P79.

# Documentation

calculatePostfix :: [Element] -> (Maybe Integer, [([Integer], Maybe Operator)]) Source #

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:

`>>>`

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

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

`>>>`

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

Negation applies to a single number:

`>>>`

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

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

`>>>`

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

The `parsePostfix`

function can be used to conveniently create an expression:

`>>>`

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

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

`>>>`

([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)`mapM_ print $ snd $ calculatePostfix $ parsePostfix "8 5 4 10 + - 3 * negate +"`

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:

`>>>`

Nothing`fst $ calculatePostfix $ parsePostfix "1 2 * +"`

`>>>`

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

### 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.

Negate | Encodes negation. Equivalent to an unary minus. Unary operator. |

Add | Encodes duplication. Makes another copy of its operand. Unary operator. |

Subtract | Encodes subtraction. Binary operator. |

Multiply | Encodes multiplication. Binary operator. |

Divide | Encodes division. Equivalent to |

Modulo | Encodes a modulo operator. Equivalent to |

#### Instances

Bounded Operator Source # | |

Enum Operator Source # | |

Show Operator Source # | |

Eq Operator Source # | |

# Supporting function

The function below is not part of the problem.

parsePostfix :: String -> [Element] Source #

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,

`>>>`

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

The operators are encoded as follows:

Operator | String |
---|---|

`Negate` | `"negate"` |

`Add` | `"+"` |

`Subtract` | `"-"` |

`Multiply` | `"*"` |

`Divide` | `"/"` |

`Modulo` | `"%"` |