= Solution
Print a prefix while following the <linked list>, counting how many closing parentheses remain. The final reciprocal can be printed without parentheses.
``
PROCEDURE printCF(f: fraction);
VAR p: fraction; opened: INTEGER;
BEGIN
p := f; opened := 0;
Out.Int(p.head, 0);
p := p.tail;
WHILE p # NIL DO
IF p.tail = NIL THEN
Out.String("+1/"); Out.Int(p.head, 0)
ELSE
Out.String("+1/("); Out.Int(p.head, 0);
opened := opened + 1
END;
p := p.tail
END;
WHILE opened > 0 DO
Out.String(")"); opened := opened - 1
END
END printCF;
``
The first <loop invariant> says that `p` is the next unprinted <linked list node>, the printed text is the correct expression prefix, and `opened` counts its unmatched opening parentheses. The final node contributes no opening parenthesis; the second <loop invariant> says that precisely `opened` closing parentheses remain. Thus `[1,2,3,4,5]` produces \b[`1+1/(2+1/(3+1/(4+1/5)))`]. A singleton prints just its head. If the first head is negative, its leading minus remains a valid prefix; subsequent heads are positive.
The precondition is a finite nonempty <continued fraction> list. Every dereference is made only for a nonnull pointer. The procedure uses $O(1)$ auxiliary space and time linear in the number of nodes, apart from printing their digits. The source's claimed strict upper bound $x_0+1$ has an exception under its stated definition: `[x0,1]` represents $x_0+1$. None of these algorithms relies on that incorrect strict bound.
Back to article page
