Here is a modified code from this post, where I only show the code for match
, and the other (helper) functions should be taken from that post verbatim:
ClearAll[match];
match[l_List] := withInfiniteIteration@match[toLL[enumerate@l], ll[], ll[]];
match[ll[{"(", p_}, tail_ll], accum_, res_] :=
match[tail, ll[{p, 0}, accum], res];
match[ll[{")", pc_}, tail_ll], ll[{po_, elems_}, ll[{popar_, elemspar_}, rest_]], res_] :=
match[tail, ll[{popar, elemspar + elems}, rest], ll[{po, pc, elems}, res]];
match[ll[{")", pc_}, tail_ll], ll[{po_, elems_}, ll[]], res_] :=
match[tail, ll[], ll[{po, pc, elems}, res]];
match[ll[{_, _}, tail_ll], ll[{po_, elems_}, rest_], res_] :=
match[tail, ll[{po, elems + 1}, rest], res];
match[ll[], ll[], res_ll] := Sort[fromLL[res]];
match[___] := $Failed;
What basically happens is that we accumulate the stack when parsing, and record the number of elements parsed into a given block of matched parentheses. When we close the block, we add the inner element count to that of the parent block. An equivalent procedure would've been to first construct a decorated tree with element counts and positions, and then traverse it to pick the positions and element counts, but here we do it on the fly as we parse.So:
lst = {"(", "x1", "x2", "(", "(", "x3", ")", "x5", "(", "x6", ")", ")", ")"};
match[lst]
(* {{1, 13, 5}, {4, 12, 3}, {5, 7, 1}, {9, 11, 1}} *)
This method should have a linear complexity in the size of the list.