...
| Code Block |
|---|
(+ 5 (* (- 1 8) (+ 7 1))) |
is pictorially
+ / \ 5 × / \ - + / \ / \ 1 8 7 1
This tree form has some advantages. To understand the more familiar
linear form, you must know about the order of operator precedence,
whereas that is unnecessary in the tree form. The tree also eliminates
the need for parentheses. The tree also gets us away from the relatively
minor concerns of the precise details of mathematical or Scheme
notation, like infix vs. prefix operators.
Consider if you were developing a computer program like DrScheme
(or, similarly, a "compiler," if you know what that is).
Such a program would take the linear form, which is convenient for
a person to type in, but then convert or
...
which encodes expressions as lists revealing their nesting structure.
The string representation for expressions is particularly unattractive for computational purposes because we have to
parse the string to understand its structure. The parsing process must understand which symbols are variables, operatorsj incorporate the precedence of infix operators.
We can define a tree formulation of simple Scheme expressions which avoids representing them as list and encodes far more information about their structure. Parsers build tree representations for programs.
To simplify the formulation of Scheme expressions as trees,
parse
...
it to the tree form
for internal use.
Since parsing is beyond the scope of this course, let's just skip straight
to the tree form.
We'll require that each addition, subtraction, multiplication, and
division has exactly two subexpressions. Of course, recursively,
each subexpression can be another addition, subtraction, multiplication,
or division. As a base case, an expression can also be a number.
...