✦ LIBER ✦
Generation of Well-Formed Parenthesis Strings in Constant Worst-Case Time
✍ Scribed by Timothy R. Walsh
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 222 KB
- Volume
- 29
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
Proskurowski and Ruskey J. Algorithms 11 1990 , 68᎐84 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.