regex to match irreducible fractions
How can I match irreducible fractions with regex?
For example, 23/25, 3/4, 5/2, 100/101, etc.
First of all, I have no idea about the gcd-algorithm realization in regex.
Update for all of you who's answering like "Y开发者_Go百科ou are using the wrong tool":
Yeah, guys, I'm realizing what regex is normally used for. It's okay. But that this question is weird is kind of its whole point.
Updated 2: The idea is to find a regex that could be helpful in a situation like:
$> echo "1/2" | grep -P regex
1/2
$> echo "2/4" | grep -P regex
So, the regex should be only a string, without using any scripts and variables. Only regex.
Actually, I already know some regex which match reducible fractions written in the unary number system.
$> echo "11/1111" | grep -P '^1/1+$|(11+)+\1+/\1+$'
11/1111
So the thing is to convert from decimal to unary number system in regex, but I don't know how.
UPDATE
Since the poster requested a single regex that matches against strings like "36/270", but says it doesn’t matter how legible it is, that regex is:
my $reducible_rx = qr{^(\d+)/(\d+)$(?(?{(1x$1."/".1x$2)=~m{^(?|1+/(1)|(11+)\1*/\1+)$}})|^)};
But, if like me, you believe that an illegible regex is absolutely unacceptable, you will write that more legibly as:
my $reducible_rx = qr{
# first match a fraction:
^ ( \d+ ) / ( \d+ ) $
# now for the hard part:
(?(?{ ( 1 x $1 . "/" . 1 x $2 ) =~ m{
^
(?| 1+ / (1) # trivial case: GCD=1
| (11+) \1* / \1+ # find the GCD
)
$
}x
})
# more portable version of (*PASS)
| ^ # more portable version of (*FAIL)
)
}x;
You can improve maintainability by splitting out the version that matches the unary version from the one that matches the decimal version like this:
# this one assumes unary notation
my $unary_rx = qr{
^
(?| 1+ / (1)
| (11+) \1* / \1+
)
$
}x;
# this one assumes decimal notation and converts internally
my $decimal_rx = qr{
# first match a fraction:
^ ( \d+ ) / ( \d+ ) $
# now for the hard part:
(?(?{( 1 x $1 . "/" . 1 x $2 ) =~ $unary_rx})
# more portable version of (*PASS)
| ^ # more portable version of (*FAIL)
)
}x;
Isn’t that much easier by separating it into two named regexes? That would now make $reducible_rx
the same as $decimal_rx
, but the unary version is its own thing. That’s how I would do it, but the original poster wanted a single regex, so you’d have to interpolate the nested one for that as I first present above.
Either way, you can plug into the test harness below using:
if ($frac =~ $reducible_rx) {
cmp_ok($frac, "ne", reduce($i, $j), "$i/$j is $test");
} else {
cmp_ok($frac, "eq", reduce($i, $j), "$i/$j is $test");
}
And you will see that it is a correct regex that passes all tests, and does so moreover using a single regex, wherefore having now passed all requirements of the original question, I declare Qᴜᴏᴅ ᴇʀᴀᴛ ᴅᴇᴍᴏɴsᴛʀᴀɴᴅᴜᴍ: “Quit, enough done.”
精彩评论