Longest segment of balanced parentheses -- an exercise in program inversion in a segment problem (Functional Pearl)

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 func...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-08
Main Authors: Shin-Cheng, Mu, Tsung-Ju Chiang
Format: Article
Language:English
Subjects:
Segments
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.2101.09699