Count elements between matching opening and closing parentheses?

Question

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}}

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

Answer 2

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}}