4

This question is purely for fun. Are regular expressions powerful enough to actually add any two positive integers? By that I mean replacing the string a+b with the numerical value of a+b.

I realize this depends on the notation we choose for numbers. Certainly if we write them as tally marks the regex is easy, just remove the plus symbol. How about numbers written in binary? Any way to do it, or convincing reasons why it is impossible?

Joe Nelson
  • 549
  • 5
  • 12
  • 1
    Well for you it's fun. And nobody takes this Question seriously. I need a Regex to add two values but I can't find anyone. Thanks for taking my opportunity to report this question!! – MartinL Feb 14 '12 at 14:03
  • Loosely related: http://stackoverflow.com/questions/9618364/is-it-possible-to-perform-addition-in-a-regex – Potherca Oct 27 '12 at 14:00

2 Answers2

1

Since this is for fun and to see power of regex:

Find prime numbers using regex - http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

manojlds
  • 290,304
  • 63
  • 469
  • 417
0

I would say no if we're talking about basic ones, since regex language is not Turing complete, maybe with powerful exsensions (eg recursive substitutions or similar tools)..

Jack
  • 131,802
  • 30
  • 241
  • 343
  • I have a feeling you're right. I've been experimenting with even incrementing a binary number, and the problem seems to be that carries can go back a potentially unbounded distance. If we could run a regex repeatedly, then yeah that could work. But I wish I could prove conclusively that it is impossible with a standard regex. – Joe Nelson Jul 28 '11 at 04:31
  • 1
    Are you sure regex with backreference are not turing complete? – Elazar Leibovich Jul 31 '11 at 08:02