You will be implementing two global_procedures Get_Tree and Put_Tree in a provided test driver. Working with your partner and before closed lab, carefully read the math definitions below and the specifications of Get_Tree and Put_Tree. Then design and code the body of the two procedures. Review your code carefully and trace it on some examples. The objective is to have code that works the first time you type it in (except perhaps for typos).
The math operations PREFIX_DISPLAY and PREFIX_DISPLAY_SUBTREES explain the format to be used when typing in a tree for the Get_Tree operation (the input format is the same that was used in the Display_Tree example discussed in class). Here are five examples of PREFIX_DISPLAY applied to trees. See if you can figure out the trees being described.
The math operations MULTILINE_DISPLAY and MULTILINE_DISPLAY_SUBTREES explain the format to be used when displaying a tree through the Put_Tree operation. Here are five examples of MULTILINE_DISPLAY applied to the same five trees as before (with an initial value of i = 0).
a |
a b c d |
a
b
c
d
e
f
g
h
|
a
b
c
d
e
f
g
|
a
b
c
d
e
f
g
h
i
j
k
|
(By the way, you can assume that the characters "(" and ")" do not appear as items in trees.)
/*!
math definition WHITESPACES (
i: integer
): string of character satisfies
if i <= 0
then
WHITESPACES (i) = empty_string
else
WHITESPACES (i) = " " * WHITESPACES (i-1)
math definition PREFIX_DISPLAY (
t: tree of character
): string of character satisfies
there exists ch: character,
subtrees: string of tree of character
(t = compose (ch, subtrees) and
PREFIX_DISPLAY (t) =
<ch> * "(" * PREFIX_DISPLAY_SUBTREES (subtrees) * ")")
math definition PREFIX_DISPLAY_SUBTREES (
s: string of tree of character
): string of character satisfies
if s = empty_string
then
PREFIX_DISPLAY_SUBTREES (s) = empty_string
else
there exists t: tree of character,
rest: string of tree of character
(s = <t> * rest and
PREFIX_DISPLAY_SUBTREES (s) =
PREFIX_DISPLAY (t) *
PREFIX_DISPLAY_SUBTREES (rest))
math definition MULTILINE_DISPLAY (
t: tree of character
i: integer
): string of character satisfies
there exists ch: character,
subtrees: string of tree of character
(t = compose (ch, subtrees) and
MULTILINE_DISPLAY (t, i) =
WHITESPACES (i) * <ch> * "\n" *
MULTILINE_DISPLAY_SUBTREES (subtrees, i+2))
math definition MULTILINE_DISPLAY_SUBTREES (
s: string of tree of character
i: integer
): string of character satisfies
if s = empty_string
then
MULTILINE_DISPLAY_SUBTREES (s, i) = empty_string
else
there exists t: tree of character,
rest: string of tree of character
(s = <t> * rest and
MULTILINE_DISPLAY_SUBTREES (s, i) =
MULTILINE_DISPLAY (t, i) *
MULTILINE_DISPLAY_SUBTREES (rest, i))
!*/
global_procedure Get_Tree (
alters Text& tree_as_text,
produces Tree_Of_Character& t
);
/*!
requires
there exists x, y: string of character,
t1: tree of character
(#tree_as_text = x * y and
x = PREFIX_DISPLAY (t1))
ensures
#tree_as_text = PREFIX_DISPLAY (t) * tree_as_text
!*/
global_procedure Put_Tree (
preserves Tree_Of_Character& t,
alters Character_OStream& outs,
preserves Integer indentation_factor
);
/*!
requires
outs.is_open = true
ensures
outs.is_open = true and
outs.ext_name = #outs.ext_name and
outs.content =
#outs.content * MULTILINE_DISPLAY (t, indentation_factor)
!*/
Note: An implementation for the following operation will be provided in the closed lab test driver:
global_procedure Print_Spaces (
alters Character_OStream& outs,
preserves Integer number_spaces
);
/*!
requires
number_spaces >= 0 and
out.is_open = true
ensures
out.is_open = true and
out.ext_name = #out.ext_name and
out.content = #out.content * WHITESPACES (number_spaces)
!*/