.Net Regular Expressions – Finding Decimal Numbers that are Divisible by Three

It’s very easy to check a decimal number is divisible by three using a simple DFA with 3 states.

A regex, therefor, is possible, but not too pretty (source):


Example: http://www.rubular.com/r/ZcRDblHg8M

Here’s another approach, using .Net’s stacks as a simple counter:

(?>             # No regrets - don't backtrack on if/else decisions.
    [0369]      # = 0 (mod 3)
    [147]       # = 1 (mod 3)
    (?:         # if possible pop 2, else push 1
    [258]       # = 2 (mod 3)
    (?:         # if possible pop 1, else push 2
(?(Sum)(?!)) # Assert nothing's left in the stack

Why? Well, I was bored while I shaved. Luckily, this regex is simple enough for Mono. Working example: http://ideone.com/Yp6Ti (ok, maybe not, mono is missing 111222)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.