Match opening and closing parentheses?

Question

Suppose I have a List of the form:

lst={"(", "(", "(", ")", "(", ")", ")", ")"}

By running Position[lst, "("] and Position[lst, ")"], I can get the positions of the opening and closing parentheses in the list. How can I match them? That is, given the lists of positions of opening and closing parentheses, how can I obtain a paired list, where each pair gives the positions of the opening and matching closing parentheses?

This is a classic problem in computer science, and I can solve it in other languages using loops, stacks, etc. I want to see the Mathematica way of solving this problem.

Answer 1

This one returns the pairs in the order they get closed:

Thread[{lst, Range@Length@lst}] //. 
  {h___, {"(", i_}, {")", j_}, t___} :> {h, t, {i, j}}

(* {{3, 4}, {5, 6}, {2, 7}, {1, 8}} *)

If other characters appear in the list they can be filtered out with Cases before doing the replacement:

lst = Characters["((()(a)))"];

Cases[Thread[{lst, Range@Length@lst}], {"(" | ")", _}] //.
  {h___, {"(", i_}, {")", j_}, t___} :> {h, t, {i, j}}

(* {{3, 4}, {5, 7}, {2, 8}, {1, 9}} *)

Answer 2

I don't know if it is the Mathematica way (or even if it is the best way), but here is how I would do it. I assume for simplicity that every entry is either an opening or a closing parenthesis (otherwise, some code explicitly ignoring any non-brackets would need to be added). Note that I'm using positionDuplicates by Szabolcs from this answer to another question.

(* from the linked answer *)
positionDuplicates[list_] := GatherBy[Range@Length[list],list[[#]]&]

(* my code *)
matchBrackets[l_]:=
  Flatten[Partition[#, 2]& /@
    positionDuplicates[
      Min@@@Partition[
        With[{fl = FoldList[#1+Switch[#2,"(",1,")",-1]&,0,l]},
             If[Last@fl !=0 || Min[fl]<0,
               Throw["Invalid parentheses"],
               fl]], 2, 1]], 1]

(* Application *)
matchBrackets[lst]
(*
==> {{1,8},{2,7},{3,4},{5,6}}
*)

Note that while errors in the bracketing are detected, I didn't make the effort to identify the exact place of the error.

The Throw for error handling is probably not the ideal way (a better way would have been to put out a warning and return the original expression unchanged, as Mathematica itself does on errors). However since I wanted to concentrate at the algorithm, not at the error handling, I didn't spend time on that aspect; maybe I'll revise that part if I have some time later this week.

Answer 3

Should be a comment, but you asked me to explain this solution:

lst = {"(", "(", "(", ")", "(", ")", ")", ")"}
StringPosition[StringJoin@lst, RegularExpression@"(?P<a>\\(([^\\(\\)]|(?P>a))*\\))"]

(* => {{1, 8}, {2, 7}, {3, 4}, {5, 6}} *)

Here, I use recursive pattern matching that is available in PCRE library, that is built into Mathematica's RegularExpression.

In detail, (?P<a>\\(([^\\(\\)]|(?P>a))*\\)) means:

• ?P<a> - give a name a to the capturing group (in this case the whole pattern)
• \\( - match open parenthesis
• ([^\\(\\)]|(?P>a))* - match zero or more occurrences of:
  • [^\\(\\)] - string without parentheses
    or
  • (?P>a) - capturing group with name a. this is the 'recursive call'
• \\) - finally match closing parenthesis

If you are interested in this recursive patterns, you should read PCRE documentation, this related question as well.

Answer 4

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.

Answer 5

I guess this is more of the StackOverflow answer, but this is how I would do it (using Javascript, I hope the syntax isn't too confusing)

var lst = ["(", "(", "(", ")", "(", ")", ")", ")"];
var pairs = [];
for(i=0;i<lst.length;i++){  
    var matched = []; 
    if(lst[i]==")"){   
       for(y=i;y>0;y--){   
            if(lst[y]=="(" && matched.indexOf(y)== -1 ){
                matched.push(y);   
                pairs.push(y+":"+i)   
                }
            }
        }
    }
}

the variable "pairs" now contain all the correct pairs.

The logic here, since I can't assume you're familiar with JS, is as follows:

• start at the beginning of lst, and check each entry until we find a closing parentheses.

• go backwards from that position, until we find an opening parentheses.

• If the opening parentheses has not been matched to a closing one already, we go ahead and add the position of the parentheses to the variable "matched", where we store all the opening parentheses that have been matched (this is how we see if it has been matched already)
• add the position of both the opening and closing parentheses to the list of matched pairs, then repeat.

this will also work even if there are other entries in "lst" that are neither kind of parentheses.

My appologies for not using the local lingo, I'm a visitor from a sister forum... Hopefully the logic behind it is understandable and helpful! =)