Matching wwR ("acddca”) using regular expressions example in C#

Question

I'm a complete noob at Regular Expressions. I've been reading through them but I still don't quite get them, like I don't even know what the '-' sign means. Can we do an example one, and walk me through it possibly? How would we do this one?

a busy cat

Basically this syntax is the string appended by its reverse.

This should match:

abccba
bCaaCb

This should not match:

lebronnorBeL
bcAacb

Thank you very much for your help!

The expression you provide only includes strings containing the symbols 0 and 1, so none of your examples are actually members of the set. — rici, Apr 24 '15 at 00:23
That's true. I'm an idiot. But bottomline is I meant reversing. — LeBron23, Apr 24 '15 at 02:22
This is just simply bracket balancing/palindrome problem. Theoretically, this is to context-free grammar, so regular expression can't match it. However, regex in the wild implements features that make it possible to match grammar outside regular languages. In .NET, Perl and PCRE, matching this grammar is possible. — nhahtdh, Apr 24 '15 at 07:36

score 1 · Answer 1 · answered Apr 23 '15 at 23:43

1

As far as i know RegEx doesn't play with such patterns.

My workaround would be like:

private bool isMirrorLikeString(string content) {
    for (int i = 0; i < (int)(content.Length / 2); i++) {
        if (content[i] != content[content.Length - 1 - i]) return false;
    }
    return true;
}

answered Apr 23 '15 at 23:43

soumasandesu

301
2
10

I can't believe I didn't think of that! I should've thought outside the box – LeBron23 Apr 24 '15 at 02:26

score 0 · Answer 2 · edited May 23 '17 at 12:01

Theoretically, the language in the question is context-free, so it cannot be described with a regular expression. However, regular expression engine in the languages and library introduces features which make them more powerful than theoretical regular expression.

In this case, it is simply asking you to detect palindrome string, except that the total length of the string is always even.

We can take the regex from this answer and modify it:

(?<N>[01])+(?<-N>\k<N>)+(?(N)(?!))

^{I dropped the .? part, which allows for odd-length palindrome, and change the . inside (?<N>.) to fit the question)}

(?<N>[01])+ captures and pushes the character into "stack" N.
(?<-N>\k<N>)+ pops from "stack" N (note the <-N>) when the item on top of the stack matches the current character (\k<N>, this is the usual back-reference to capturing group N).
(?(N)(?!)) checks that if there is anything left on the stack N, then fail and backtrack.

Note that this regex is unique to .NET engine due to balancing group feature in .NET. Perl and PCRE can also match the language in the question, but with different feature (routine call).

Matching wwR ("acddca”) using regular expressions example in C#

2 Answers2