Introduction to Programming

Assignment 6

Date: Wed, 3 November 2004

Due on: Wed, 10 November 2004

Expression Evaluation

Consider infix arithmetic expressions using the operators +,-,* without parentheses and without any assumptions about the order in which to evaluate subexpressions. Thus, an expression such as 6*3+2 may be evaluated as (6*3)+2 = 20 or 6*(3+2) = 30, depending on the order of evaluation.

Recall that the order of evaluation of an expression can be unambiguously described using a tree. Consider the following declaration in Haskell:

           data Expr = Value Int | 
                       Add Expr Expr | 
                       Sub Expr Expr | 
                       Mult Expr Expr
    

Write the following functions in Haskell:

1. show :: Expr -> String

   that displays an Expr tree in human readable form as an expression with parentheses. For instance,

                show (Mult (Value 6) (Add (Value 3) (Value 2)))
            

   should evaluate to

               "(6*(3+2))"
            

2. parseExpr :: String -> [Expr]

   that takes as input an arithmetic expression without parantheses in the form of a String (e.g. "6*3+2") and generates as output a list of all valid Expr trees for this expression.

3. evalExpr :: String -> [Int]

   that takes as input an arithmetic expression without parentheses in the form of a String (e.g. "6*3+2") and generates as output a list of all valid evaluations for this expression, without duplicates.

In parts 2 and 3, you may assume that each integer that appears in the input expression is a single digit positive integer. You may also assume that the input expression is legal - that is, it is guaranteed to correspond to at least one Expr tree.

Submit all your code as a single Haskell file.