Longest segment of balanced parentheses — an exercise in program inversion in a segment problem

Shin-Cheng Mu and Tsung-Ju Chiang. Submitted.

Given a string of parentheses, the task is to find a longest consecutive segment that is properly bracketed. We find it an interesting problem because it involves two techniques: the usual approach for solving segment problems, and the converse-of-a-function theorem — through which we derived an instance of shift-reduce parsing.

[arXiv:2101.09699]

Leave a Comment

Your email address will not be published. Required fields are marked *