TAOCP 2.4 Exercise 3

Section 2.4: Multilinked Structures

Exercise 3. [**] [22] The PL/I language accepts data structures like those in COBOL, except that any sequence of level numbers is possible. For example, the sequence

1 A                 1 A
3 B                 2 B
5 C   is equivalent to   3 C
4 D                 3 D
2 E                 2 E

In general, rule (a) is modified to read, "The items of a group must have a sequence of nonincreasing level numbers, all of which are greater than the level number of the group name." What modifications to Algorithm A would change it from the COBOL convention to this PL/I convention?

Verified: yes
Solve time: 1m13s

Algorithm A needs only one change in the step that determines the parent of a newly read item. Under the COBOL convention, if the new item has level number $L$, its parent is required to have level number $L-1$; hence the algorithm moves upward until it finds level $L-1$.

For the PL/I convention, replace this test by: move upward until the most recent item whose level number is strictly less than $L$ is found. That item becomes the parent of the new node. Equivalently, maintain the stack of currently open groups exactly as before, but when an item of level $L$ is read, repeatedly delete stack entries whose level number is $\ge L$; then attach the new item as the last child of the remaining top stack entry and push the new item onto the stack.

No other modification is required. The stack invariant becomes: its level numbers are strictly increasing, and the parent of each item is the nearest preceding item whose level number is smaller. This realizes the PL/I rule that the items of a group have a sequence of nonincreasing level numbers, all greater than the level number of the group name.