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?

Improve this question
$\endgroup$
1
  • $\begingroup$ On the last point, FullForm[x___] is Pattern[x,BlankNullSequence[]] not Sequence $\endgroup$ Commented May 10, 2021 at 16:43

2 Answers 2

Reset to default
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.

Improve this answer
$\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$ Commented May 11, 2021 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$ Commented May 11, 2021 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$ Commented May 11, 2021 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$ Commented May 11, 2021 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]"

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well, stuff like F[c,a,c,z,c] is legit input in my case. $\endgroup$ Commented May 11, 2021 at 8:08

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.