# ICS 269, Fall 1998: Theory Seminar

## November 6, 1998:

Generation of Well-Formed Parenthesis Strings in Constant
Worst-Case Time

Junyu Peng, ICS, UC Irvine

Proskurowski and Ruskey (*J. Algorithms 11(1990)*)
published a recursive algorithm for generating well-formed
parenthesis strings of length 2*n* and challenged the reader
to find a loop-free version of their algorithm. We present two
nonrecursive versions of their algorithm, one of which generates
each string in O(*n*) worst-case time and requires space for
only O(1) extra integer variables, and the other generates each
string in O(1) worst-case time and uses O(*n*) extra
space.