Regex counting characters on two sides

Question

I'm not entirely sure if the title makes any sense at all but I'm not sure how to explain any better. I'm trying to match a string that starts with one or more ('s and ends with the same amount of )'s. I've tried many different things but I can't figure out how to do this in regex, or if it's possible at all! Can anyone send me in the right direction?

Examples

Match: (a)

Match: ((a))

Don't match: ((a)

Don't match: ((a)))

etc etc etc, you get the point.

This is not something that should be done with regex. Regex is really bad at counting. — Aran-Fey, Jun 04 '18 at 18:47
@Aran-Fey But is it possible? And if so, would it have a big effect on performance? Otherwise I might have to add validation in C# — Metoniem, Jun 04 '18 at 18:49
I'm pretty sure it's possible in most regex flavors, but I don't remember how. It requires some god-tier regex skill. — Aran-Fey, Jun 04 '18 at 18:53
Why *must* you use a Regex for this? What will you be doing after you match or don't match the characters? — Dour High Arch, Jun 04 '18 at 19:00
You may, [`^(?>(?$)+.*?(?<-o>$)+)$(?(o)(?!))`](http://regexstorm.net/tester?p=%5e%28%3f%3e%28%3f%3co%3e%5c%28%29%2b.*%3f%28%3f%3c-o%3e%5c%29%29%2b%5cr%3f%29%24%28%3f%28o%29%28%3f!%29%29&i=%28a%29%0d%0a%28%28a%29%29%0d%0a%0d%0a%28%28a%29%0d%0a%28%28a%29%29%29&o=m), but you do not have to. If there must be no `(` and `)` inside the string, [`^(?>(?$)+[^()]*(?<-o>$)+)$(?(o)(?!))`](http://regexstorm.net/tester?p=%5e%28%3f%3e%28%3f%3co%3e%5c%28%29%2b%5b%5e%28%29%5d*%28%3f%3c-o%3e%5c%29%29%2b%5cr%3f%29%24%28%3f%28o%29%28%3f!%29%29&i=%28a%29%0d%0a%28%28a%29%29%0d%0a%28%28a%29&o=m). — Wiktor Stribiżew, Jun 04 '18 at 19:02
@DourHighArch Not _must_, I could do it in C# aswell, but I would have liked to have a slightly more complete regular expression. (I'm making a regex to match static js variables, and their values can be wrapped in parenthesis) — Metoniem, Jun 04 '18 at 19:05
Wait, are you trying to “count characters on two sides” or are you “making a regex to match static js variables” because those are two completely different problems. — Dour High Arch, Jun 04 '18 at 19:08
@DourHighArch I know they are, but I'm only having trouble with figuring out of there's an equal amount of parenthesis on both sides of the value, which makes my problem "counting characters on two sides" — Metoniem, Jun 04 '18 at 19:09
Does `^$(?:[^()]|(?\()|(?<-open>$))+(?(open)(?!))\)$` work for you? — Wiktor Stribiżew, Jun 04 '18 at 19:11
@WiktorStribiżew That looks like it's what I need, thanks! Do you happen to know what I should Google to actually understand what the `(?<-o>)` part means? I'd love to learn how it works (edit: this was a reply to your previous comment) — Metoniem, Jun 04 '18 at 19:12
@WiktorStribiżew Yup! That one does indeed work aswell. Thanks :) My question about what that `-open` group is called remains though haha — Metoniem, Jun 04 '18 at 19:15
@WiktorStribiżew I'll hit the "that solved my question!" button, thanks for helping out :) — Metoniem, Jun 04 '18 at 19:19
Here is [another post that will help you dive into balanced constructs](https://stackoverflow.com/questions/17003799/what-are-regular-expression-balancing-groups/17004406#17004406). — Wiktor Stribiżew, Jun 04 '18 at 19:20
Woah @WiktorStribiżew I just read through that and understand how it works now! Thanks :) that's super interesting & clever — Metoniem, Jun 04 '18 at 19:33
I figured it out how to do it without fancy C# features; all you need are lookarounds: `^(?:$(?=.*((?(1)\1|)$)$))+(?!$).*(?<!$)\1$`. Basically, it matches 1 character at a time, and for each consumed opening brace it also captures an additional closing brace in a capture group. — Aran-Fey, Jun 04 '18 at 20:01

score 0 · Answer 1 · answered Jun 04 '18 at 18:51

You can do it, relatively easily, with a stack data structure. You process the string character by character, and you push when you meet ( and pop when you meet ). If at the end of the string processing you have arrived with empty stack than the string is valid. Otherwise, if you meet ')' with empty stack then the string is not valid.

To count, just maintain a variable of the maximum size that the stack will reach.

Regex counting characters on two sides

1 Answers1