| 3. |
(a) Rewrite the
following infix expressions in a fully bracketed form, and then convert them into
their post-fix forms. |
|
|
|
(i) (A + B) x C - D |
[2] |
|
|
(ii) A x B / (C + D ^ E) / F ^ G |
[3] |
|
|
(iii) A ^ B - C x D + E / F / (G + H) |
[4] |
|
|
|
|
|
(b) Given the
following type definition for a binary tree: |
|
|
|
|
|
|
|
where a leaf node contains Nil entries for
both the Left and Right sub-trees. |
|
|
|
(i) Write a recursive procedure that
traverses the tree using a post-order traversal, printing the data item Data
during the traversal. |
[5] |
|
|
(ii) Write a recursive function that
determines the height of a binary tree. |
[6] |