Uniform Random Generation of Balanced Parenthesis Strings
- 1 January 1980
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 2 (1) , 122-128
- https://doi.org/10.1145/357084.357091
Abstract
The empirical testing of error repair schemes for skeletons of source programs in a block-structured language leads to the problem of generating balanced parenthesis strings in a uniform random manner. An efficient generator which works from left to right must compute the correct probability for the next symbol at each stage of the generation. The associated enumeration problem may be solved by adopting a geometric interpretation usually associated with random walk problems. This solution leads immediately to an O ( n ) algorithm for the generator.Keywords
This publication has 1 reference indexed in Scilit:
- Phas-structure productions in PL/ICommunications of the ACM, 1967