Here is a recursive solution based on linked lists. It will not be extremely fast, but reasonably efficient for the top-level code, and I think it clearly expresses the recursive nature of parsing. These are some helper functions:
These are conversion functions to and from linked list:
ClearAll[ll, toLL, fromLL];
SetAttributes[ll, HoldAllComplete];
toLL[l_List] := Fold[ll[#2, #1] &, ll[], Reverse@l];
fromLL[l_ll] := List @@ Flatten[l, Infinity, ll];
They are described in more detail here. Two more functions we will need:
ClearAll[withInfiniteIteration];
withInfiniteIteration =
Function[code, Block[{$IterationLimit = Infinity}, code], HoldAll];
ClearAll[enumerate];
enumerate[l_List] := Transpose[{l, Range[Length[l]]}];
The actual recursive function to match the parentheses:
ClearAll[match];
match[l_List] :=
withInfiniteIteration@match[toLL[enumerate@l], ll[], ll[]];
match[ll[{"(", p_}, tail_ll], accum_, res_] :=
match[tail, ll[p, accum], res];
match[ll[{")", pc_}, tail_ll], ll[po_, at_ll], res_] :=
match[tail, at, ll[{po, pc}, res]];
match[ll[], ll[], res_ll] := Sort[fromLL[res]];
match[___] := $Failed;
Basically, match
maintains the stack in the "functional" way. So:
match[lst]
(* {{1, 8}, {2, 7}, {3, 4}, {5, 6}} *)
Once again, no speed ambitions here, but I think that conceptually, this is a very simple solution, and the algorithmic complexity of this solution should also be fine.
StringPosition[StringJoin@lst, RegularExpression@"(?P<0>\\(([^\\(\\)]|(?P>0))*\\))"]
$\endgroup$ – Dan Oak Mar 20 '15 at 18:05