Introduction to Programming
                   Assignment 4, 8 Oct 2008
                      Due Fri 17 Oct 2008


                      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:

(a) 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))"

(b) parseExpr :: String -> [Expr]

    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 Expr trees for this
    expression. 

(c) evalExpr :: String -> [Int]

    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 evaluations for this
    expression, without duplicates.

In (b) and (c), 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.