# Custom bracket parser

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?

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

## 2 Answers

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.

• 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? – Hauke Reddmann May 11 at 8:06
• It would be easier if you first gave a good-sized set of easy and difficult cases and their expected answers. – Roman May 11 at 14:47
• 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={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; – Hauke Reddmann May 11 at 17:49
• 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. – Hauke Reddmann May 11 at 17:52

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]"

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