Haskell Programming

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.

4. Write a function called rpnTrans that takes a PExp and (given correct input) returns a String of an equivalent arithmetic expression in infix notation, with the correct corresponding order of operations enforced using parentheses. This translation process is still prone to failure on bad inputs, so we should use a similar Either a b conguration (as in evalSafe), but instead of creating a special type to represent it, we will return a String in the failure case as well. Formulating the correct type signature of rpnTrans is left to the student.

Here are examples of how rpnTrans should work:

HW4*> rpnTrans [Val 1, Val 1, Plus]

Right "(1 + 1)"

HW4*> rpnTrans [Val 2, Val 4, Plus, Val 3, IntDiv]

Right "((2 + 4) / 3)"

HW4*> rpnTrans [Val 2]

Right "2"

HW4*> rpnTrans [Plus]

Left "Bad Input."