# Count elements between matching opening and closing parentheses?

Suppose I have a List of the form:

lst={"(", "x1", "x2", "(", "(", "x3", ")", "x5", "(", "x6", ")", ")", ")"}


For each pair of matching opening and closing parenthesis, I need to count the number of x's inside. More precisely, I need to obtain a list of triplets, {op, clos, no}, where op and clos are the positions of the matching ( and ), and no is the number of x's inside. The list of triplets should contain one triplet per matching pair of parenthesis. I am sure there are ways to do this using loops, but I want to see the Mathematica way.

For the example lst defined above, the expected result is:

{{1,13,5}, {4,12,3}, {5,7,1}, {9,11,1}}


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.

Reap[
lst //.
{f___, PatternSequence["(", a__?(FreeQ["(" | ")"]), ")"], l___} :>
(Sow[{Length[{f}] + 1, Length[{f}] + Length[{a}] + 2, Count[{a}, Except[Null]]}];
{f, Null, a, Null, l}
);
] // Last // Last // Reverse


{{1, 13, 5}, {4, 12, 3}, {9, 11, 1}, {5, 7, 1}}