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. Problem 1. Write a function called rpnParse, that parses a String and returns a PExp. Input strings for this function are tokens that are either numbers or operators separated by whitespace. Numbers can be an arbitrarily long strings of digits. Note: You do not need to validate that the input is a well-formed, RPN expression. Hint: Converting String to other data types (like Int) can be done using the read function in Haskell. Review the documentation and examples of this function online to see how it works.

Here are examples of how rpnParse should work: HW4*> rpnParse "200 + - * /"

[Val 200,Plus,Minus,Mul,IntDiv]

HW4*> rpnParse "+ - * / 200"

[Plus,Minus,Mul,IntDiv,Val 200]