13
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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}} *)
$\endgroup$
  • $\begingroup$ wow, this one is my favorite! but it wont work if other characters are in the list. $\endgroup$ – sacratus Mar 21 '15 at 1:12
  • $\begingroup$ @sacratus, other characters can be removed after appending the position numbers but before doing the replacement (see edit). $\endgroup$ – Simon Woods Mar 21 '15 at 12:16
  • 1
    $\begingroup$ Not to diminish this answer (I upvoted it), but just for future visitors who might not know it: this one will in general have a quadratic complexity in the size of the list with parentheses (which was the main reason I discarded this version myself, when answering). $\endgroup$ – Leonid Shifrin Mar 22 '15 at 18:08
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ this no longer works - RegularExpression::msg84: Group name must start with a non-digit in RegularExpression[(?P<0>(([^()]|(?P>0))*))]. >> $\endgroup$ – M.R. Mar 19 '16 at 3:23
  • $\begingroup$ @M.R.: works on Mathematica 10. how did you find this error? $\endgroup$ – Dan Oak Mar 20 '16 at 12:42
  • 1
    $\begingroup$ I get the same error as @M.R. with version 11.2.0. To make the pattern working it is sufficient to change the name of the group from 0 to a. $\endgroup$ – Alexey Popkov Jan 7 '18 at 9:32
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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! =)

$\endgroup$
  • $\begingroup$ Hi ! This is Mathematica.SE, so, sadly, your answer is off-topic. $\endgroup$ – Sektor Mar 20 '15 at 23:28
  • 2
    $\begingroup$ yeah...sorry about that, this popped up on the right when I was visiting StackOverflow, I saw the title and thought "hey, I can help with that!" Figured the OP was really asking for a method to solve it, so I thought I'd provide my 2 cents.Like I said in the end of the answer, I hope the underlying logic might still be useful (and understandable)! $\endgroup$ – Anders Martini Mar 21 '15 at 0:00
  • 2
    $\begingroup$ Thanks for your answer. It is true that other languages are off-topic here but that doesn't mean that Mathematica or code for it is strictly necessary for a good answer. If one chooses to answer without it he should use pseudocode and a written description of the algorithm proposed. You already provided the latter, and in this case the JS seems not far from pseudocode. Finally there are cases when code in another language is still directly useful to Mathematica users. All in all, +1 $\endgroup$ – Mr.Wizard Mar 21 '15 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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