ICS Theory Group

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 2n 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.