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

2 Answers 2


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:

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", ")", ")", ")"};


(* {{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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.