Introduction to Programming
Assignment 6, 5 Nov, 2008
Due Fri 21 Nov, 2008
Note: Remember to always supply a type definition for every
function you write, including any auxiliary functions that
you may define to solve the given problem.
Expression evaluation:
Consider infix arithmetic expressions over integers 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.
Write a function
maxval :: String -> (Int,String)
that computes the largest value that can be obtained by
bracketing the expression suitably and also prints out a
bracketed expression that achieves this maximum value.
You may assume that each integer value in the input expression is
a single digit.
Use memoization, with a simple list based memo to remember
already computed values.