Haskell Programmin

Background Reverse Polish Notation (RPN) and Polish Notation (PN) are alternatives to the more commonly seen inx notation for arithmetic. Unlike inx notation, RPN and PN do not require conventions regarding the order of operations. Instead, the order of evaluation is dictated by the syntax. With RPN, operands are followed by their operators and evaluated accordingly. In this assignment, we will implement an RPN interpreter similar to what you might see in an HP calculator. Here is the declaration for the language you will write the interpreter for: data Op = Val Int | Plus | Minus | Mul | IntDiv deriving (Show , Eq) type PExp = [Op] Our operators (i.e., Plus, Minus, Mul, and IntDiv) and operands are both represented by the Op type. Whole arithmetic expressions in RPN are represented as lists of operations. Evaluation for RPN works by reading a stream of inputs from front to back. If a number (i.e., Val 5) is read, it (i.e., 5) is pushed onto a stack. If any operator is read, its operands are popped o of the stack, the operation is performed with them and the result is pushed back onto the stack. The topmost value on the stack becomes the rightmost argument to an operator. For example,the input 2 5 - should evaluate to -3. Correct computations in RPN result in an empty input and a stack with only one number value. Stacks with more than one value in them at the end of evaluation result from malformed input.

2. Write a function called eval, that evaluates an RPN expression. This function should be typed as PExp -> Int. Cases of bad input and evaluation should result in a call to the Haskell error function. Hint: You may need to dene a helper function that takes a stack (represented using a list) and a PExp and returns an Int. Then, use the helper function to dene eval.

Here are examples of how eval should work:

HW4*> eval [Val 4, Val 2, IntDiv]

2

HW4*> eval [Mul]

*** Exception: Bad Input.

HW4*> eval [Val 4,Val 0,IntDiv]

*** Exception: Cannot divide by zero!

HW4*>