3
$\begingroup$

I have a function $F$ taking arbitrarily many arguments from ${a,c,z}$ where practically (technically it isn't) $a$ works as an opening bracket and $z$ as a closing. ($c$ stands for a value.) Double brackets around a value shall cancel, but if I write F[v___,a,a,x___,z,z,w___]:=F[v,x,w] it obviously flies me in the face since e.g. in F[a,A,c,z,a,c,Z,z] the marked $Z$ does not close the marked $A$. Clearly $F[c,z,a,c]$ is syntax nonsense, but unfortunately, just counting brackets (e.g. by M[F[x___]]:=F[x]/.{a->1,c->0,z->-1,F->Plus}; ) is not enough to recognize this. I need a "Catalan Counter": if at any point the partial sum of $M$ is $<0$, the rule may not apply. I surely could hack this together in half an hour, but speed might be relevant. So, anyone can come up with an elegant solution F[v___,a,a,x___,z,z,w___]:=F[v,x,w]/;Br[x] where $Br$ returns true iff $x$ is correctly bracket-matched?

(EDIT: M[F[x___]] := F[x] /. {a -> 1, c -> 0, z -> -1, F -> List} // Accumulate // Min; - is that a good idea? If it returns $<0$, I'd say the brackets don't match.)

Additional headscratcher: M[x___]:=x/.{a->1,c->0,z->-1,Sequence->Plus}; would be more elegant...but doesn't work. Why doesn't the pattern matcher recognize $x$ as a sequence? Can I somehow "guide" it?

$\endgroup$
1
  • $\begingroup$ On the last point, FullForm[x___] is Pattern[x,BlankNullSequence[]] not Sequence $\endgroup$ – flinty May 10 at 16:43
2
$\begingroup$

Recursive double-bracket removal:

F::unmatched = "brackets in `1` are unmatched";
F[v___, a, a, x : Except[a | z] ..., z, z, w___] := F[v, x, w]
F[x : Except[a | z] ...] := G[x]
F[x___] := Message[F::unmatched, {x}]

Try it out:

F[]
(*    G[]    *)

F[a, b, c]
(*    F::unmatched: brackets in {a,b,c} are unmatched    *)

F[a, a, c, z, a, c, z, z]
(*    F::unmatched: brackets in {a,a,c,z,a,c,z,z} are unmatched    *)

F[a, a, z, z, z]
(*    F::unmatched: brackets in {z} are unmatched    *)

F[a, a, b, z, z, d, a, a, c, z, z, e]
(*    G[b, d, c, e]    *)

You can replace G with whatever it is you want to do with the matched forms.

$\endgroup$
4
  • $\begingroup$ Looks cool, but I always hesitate to upvote an answer that uses (argl!) recursion. (Also I have first to understand the syntax which is new for me, although I intuitively grasp the semantics :-) I meanwhile corrected my idea, it works now: Again, turn a,c,z into 1,0,-1 and Accumulate. If the Min and the Last of that list are zero, match. Also, F[] would return infinity/error and has to be if-caught. Code: B[L_]:=Min[L]==0&&Last[L]==0; M[F[x___]]:=If[F[x]===F[],True,F[x]/.{a->1,c->0,z->-1,F->List}//Accumulate//B]; Mind to do a timing test for the two variants for me? $\endgroup$ – Hauke Reddmann May 11 at 8:06
  • $\begingroup$ It would be easier if you first gave a good-sized set of easy and difficult cases and their expected answers. $\endgroup$ – Roman May 11 at 14:47
  • $\begingroup$ Even the smallest version is already too long for a comment, how do I UL it? The generated completed list goes exponential with $n$, timing thus should be easy. The recursive (yikes) list code:L[1]={F[],F[a,z],F[c],F[a,c,z]}; J[F[x___],F[y___]]:={F[x,y],F[a,x,y,z]}; L[n_]:=Table[Outer[J,L[k],L[n-k]],{k,1,n/2}]//Flatten//Union; $\endgroup$ – Hauke Reddmann May 11 at 17:49
  • $\begingroup$ It would be sufficient to test double bracket elimination: F[x___,a,a,v___,z,z,y___]:=F[x,v,y]/;M[F[v]]; where my M=Br from above I compute this way: T[F[x___]]:=If[F[x]===F[],{0},F[x]/.{a->1,c->0,z->-1,F->List}]; B[L_]:=Min[L]==0&&Last[L]==0; M[F[x___]]:=T[F[x]]//Accumulate//B; Iff in ((e)) the expression e is bracket-matched, it will be reduced to e. $\endgroup$ – Hauke Reddmann May 11 at 17:52
1
$\begingroup$

You could make checks to ensure that the input is correct like e.g.:

F[v___, a, a, x___, z, z, w___] := 
 Module[{all = {v, a, a, x, z, z, w}, res},
  If[Count[all, a] != Count[all, z], 
   Print["Number of Brackets do not match"], Return];
  res = all //. {x1___, a, a, Shortest[x2___], z, z, x3___} -> {x1, 
      x2, x3};
  If[! FreeQ[
     t = res //. {x1___, a, Shortest[x2___], z, x3___} :> {x1, x2, 
         x3}, a | z], Print["Brackets do not match"]; Return];
  ]

Note, this interprets a,a...z,z strongly. E.g. "F[1, 2, a, a, 3, z, 5, a, 4, z, z, 5, 6]" is not accepted, but it could be interpreted as: "F[1, 2,( a, (a, 3, z), 5, (a, 4, z), z), 5, 6]"

$\endgroup$
1
  • $\begingroup$ Well, stuff like F[c,a,c,z,c] is legit input in my case. $\endgroup$ – Hauke Reddmann May 11 at 8:08

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.