Print a prefix while following the linked list, counting how many closing parentheses remain. The final reciprocal can be printed without parentheses.The first loop invariant says that
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;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 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 auxiliary space and time linear in the number of nodes, apart from printing their digits. The source's claimed strict upper bound has an exception under its stated definition:
[x0,1] represents . None of these algorithms relies on that incorrect strict bound. Articles by others on the same topic
There are currently no matching articles.