Longest segment of balanced parentheses: an exercise in program inversion in a segment problem. (25th November 2021) - MU, SHIN-CHENG; CHIANG, TSUNG-JU
Abstract: Given a string of parentheses, the task is to find the longest consecutive segment that is balanced, in linear time. We find this problem interesting because it involves a combination of techniques: the usual approach for solving segment problems and a theorem for constructing the inverse of a function—through which we derive an instance of shift-reduce parsing.