Problems.P79

Description

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

Synopsis

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

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

Expand

The monad transformers for the State, Maybe, and Writer monads are StateT, MaybeT, and WriterT, respectively.

data Element Source #

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

Constructors

 Operator Operator Operand Integer

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Monads MethodsshowList :: [Element] -> ShowS # Source # Instance detailsDefined in Problems.Monads Methods(==) :: Element -> Element -> Bool #(/=) :: Element -> Element -> Bool #

data Operator Source #

Encodes an operator for a mathematical expression.

Constructors

 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 div. Binary operator. Modulo Encodes a modulo operator. Equivalent to mod. Binary operator.

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Monads Methods Source # Instance detailsDefined in Problems.Monads MethodsenumFrom :: Operator -> [Operator] #enumFromTo :: Operator -> Operator -> [Operator] # Source # Instance detailsDefined in Problems.Monads MethodsshowList :: [Operator] -> ShowS # Source # Instance detailsDefined in Problems.Monads Methods

# Supporting function

The function below is not part of the problem.

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:

OperatorString
Negate"negate"
Add"+"
Subtract"-"
Multiply"*"
Divide"/"
Modulo"%"