CS 315 Assignment 6: Basic Trees
Due: October 12, 2011.
All of the following functions that operate on trees should be recursive.
Some functions that you may need are provided in the file
Cons.java . This assignment may be done in Java or in Lisp.
- Write a function maxbt(Object tree)
that finds the maximum value in a binary tree of Integer.
For this function, we will assume that both the first and
rest of a Cons can be subtrees. We will assume
that every element of the tree is a Cons (which can be
tested with consp and then cast as (Cons)),
null, or Integer. We will assume that every
Integer is greater than Integer.MIN_VALUE.
Example: (maxbt '((1 7) (-3 2) (((8)))) ) = 8
- An algebraic expression can be written as a linked list tree:
an expression is either a number (Integer or Double),
a symbol (String), or a list (op lhs rhs)
where op is an operator (String) and lhs
(left-hand side) and rhs (right-hand side) are expressions.
The functions op, lhs and rhs are provided.
Write a function Cons vars(Object expr) that returns a set
of the variables in an expression. Note that the op and
numbers are not variables. The result is a set (list) of variables
in any order; the union function is provided.
Example: (vars '(= f (* m a))) = (f m a)
- Write a function
boolean occurs(Object value, Object tree) that tests whether
the value occurs anywhere in the expression tree.
We will assume that the value has a .equals() method
and is not a Cons.
Example: (occurs 'm '(= f (* m a))) = true
- Write a function Integer eval(Object tree) that
evaluates (finds the value of) an expression tree where the leaves
are Integer. The value of an Integer expression
is the expression
itself. If the expression is a Cons, first find the value of
its arguments (lhs and rhs), then perform the
operation denoted by the op. The possible operations are
+ - * / expt . (expt x n) raises x to the power
n; a function pow is provided. Note that -
could have either one operand (minus) or two operands (difference);
all other operations are assumed to be binary.
Note: if you use Lisp, call your function
myeval; eval is the Lisp interpreter.
Example: (eval '(+ 3 (* 5 7))) = 38
- Write a function
Integer eval(Object tree, Cons bindings)
that evaluates an expression tree where the leaves are Integer or are
variables whose values are given in the bindings.
bindings is an association list, ((var value) ...),
that gives values for variables. This version of eval is
an easy extension of the previous one. The function assoc
Example: (eval '(+ 3 (* 5 b)) '((b 7))) = 38
- Write a function Cons english(Object tree) that
translates an expression tree into a list of English words (Strings).
If the tree is a leaf, the translation is just a list of that tree.
For an expression, make a list containing "the", an
appropriate English word for the operator, and the operands connected
by "of" and "and".
(english '(+ 3 (* b 7))) =
(the sum of 3 and the product of b and 7)
- There is a close relationship between programming languages
and trees. A compiler performs parsing, which converts a
character string in a programming language to a tree.
Unparsing, converting a tree to a program, is also useful.
Write a function String tojava(Object tree) that translates
an expression tree to a String that is a line of Java code.
The line of Java code should be terminated by a semicolon character.
We will assume that the expression can contain the operators
= + - * / as well as single-argument functions such as
Operators have precedence, which determines the
order in which operations are performed when an expression is not
parenthesized. We will assume that = has precedence 1,
+ - have precedence 5, and * / have precedence 6.
A subexpression needs to be parenthesized if its precedence is less
than or equal to the precedence of its surroundings; otherwise, it
should not be parenthesized. Make an auxiliary function that
includes precedence as an argument. The starting precedence can be 0,
so that any operator will be higher in precedence.
Example: (tojava '(= x (* (+ a b) c))) = "x=(a+b)*c;"
We will assume that a unary minus should always be parenthesized,
and that it has a precedence of 6.
For functions that are not in the operator list, such as sin,
make the name be Math. followed by the function name, and make
a function call form. For example, (sin x) would become