正则表达式匹配不可约分数

Question

如何将不可约分数与正则表达式匹配？

例如，23/25、3/4、5/2、100/101等。

首先，我对正则表达式中的gcd算法实现一无所知。

更新对于所有回答“你使用了错误的工具”的人：

是的，伙计们，我意识到正则表达式通常用于什么。没关系。但这个问题很奇怪，这就是它的全部意义所在。

更新2：这个想法是找到一个在以下情况下可能有用的正则表达式：

$> echo "1/2" | grep -P regex
1/2
$> echo "2/4" | grep -P regex

因此，正则表达式应该只是一个字符串，而不使用任何脚本和变量。只有正则表达式。

实际上，我已经知道一些匹配一元数字系统中编写的可约分数的正则表达式。

$> echo "11/1111" | grep -P '^1/1+$|(11+)+\1+/\1+$'
11/1111

所以问题是在正则表达式中从十进制转换为一元数字系统，但我不知道如何。

Answer 1

更新

由于海报要求一个与“36/270”等字符串匹配的正则表达式，但表示它的可读性并不重要，因此该正则表达式是：

my $reducible_rx = qr{^(\d+)/(\d+)$(?(?{(1x$1."/".1x$2)=~m{^(?|1+/(1)|(11+)\1*/\1+)$}})|^)};

但是，如果像我一样，您认为难以辨认的正则表达式是绝对不可接受的，您可以将其写得更清晰：

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;

您可以通过将与一元版本匹配的版本与与十进制版本匹配的版本分开来提高可维护性，如下所示：

# 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;

将其分成两个命名的正则表达式不是更容易吗？现在，这将使 $reducible_rx 与 $decimal_rx 相同，但一元版本是它自己的东西。我就是这样做的，但是原始海报想要一个正则表达式，因此您必须插入嵌套的正则表达式，正如我在上面首先介绍的那样。

无论哪种方式，您都可以使用以下方法插入下面的测试工具：

    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");
    }

您将看到它是一个通过所有测试的正确正则表达式，而且使用单个正则表达式来实现这一点，因此现在已经通过了原始问题的所有要求，我声明Qᴜᴏᴅ ᴇʀᴀᴛ ᴅᴇᴍᴏɴsᴛʀᴀɴᴅᴜᴍ：“退出，够了。”

Answer 2

不，这是不可能的。就像一个优秀的计算机科学家一样，我会忽略工具正则表达式的细节，并假设您在询问是否存在正则表达式。我对正则表达式的功能没有足够的了解，无法确保它仅限于正则表达式。抛开这个警告不谈，继续表演吧。

改写一下我们得到：

设 L 为语言{"a/b"|其中 a 和 b 是以基数 r 和 a 和 b 编码的自然数> 互质}。 L 是正则吗？

假设这样的语言是正规的。那么存在一个可以决定L中的成员资格的DFA。令 N 为此类 DFA 的状态数。素数有无数个。由于素数的数量是无限的，因此存在任意多个素数大于基数r中N位可编码的最大数。 （注意：最大的数字显然是 r 的 N 次方。我使用这种奇怪的措辞来展示如何容纳一元。）选择 N+ 1 大于该数字的素数。所有这些数字都使用至少 N+1 位数字（以基数 r 表示）进行编码。枚举这些素数 p₀ 到 pₙ。令 sᵢ 为读取 / 后 pᵢ 的状态。根据鸽巢原理，有 N 个状态和 N+1 sᵢ 状态，因此至少存在一对索引 ( j,k) 使得 sⱼ = sₖ。因此，从 DFA 的初始状态开始，输入 pₖ/ 和 pⱼ/ 会导致相同的状态 sⱼ （或 sₖ< /code>) 和 pⱼ 和 pₖ 是不同的素数。

L 必须接受所有不同素数对 p/q，因为它们是互质的，并拒绝所有被自身除 p/p 的素数作为 p 与 p 不互质。现在该语言接受 pⱼ = pₖ，因此存在从使用字符串 pₖ 的 sⱼ 到接受状态的状态序列，将此序列称为 <代码>β。令 α 为从初始状态开始读取 pₖ 的状态序列。从字符串 pₖ/pₖ 的初始状态开始的 DFA 状态序列必须与 α 后跟 相同β。该序列从初始状态开始，进入 sₖ（通过读取输入 pₖ），并通过读取 pₖ 达到接受状态。 DFA 接受 pₖ/pₖ，并且 pₖ/pₖ 位于 L 中。 pₖ 与 pₖ 不互质，因此 pₖ/pₖ 不在 L 中。矛盾。因此语言L是不规则的，或者不存在正则表达式。

Answer 3

如果您以一元形式编写数字，并使用“：”作为除号，我认为这与可约分数匹配：

/^1+:1$|^(11+):\1$|^(11+?)\2+:\2\2+$/

然后您可以使用 !~ 查找不匹配的字符串。

基于此：http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

Answer 4

你可以知道，以(0,5)结尾的数字可以被(5)整除，或者以(2,4,6,8,0)结尾的数字可以被2整除。

对于3,4,6,7， 8,9 作为除数，我不期望有这种可能性，对于任意除数也不是这样。

我猜你知道决定被 3 整除的方法 - 构建递归交叉和，它必须能被 3 整除，才能使数字可整除。因此，您可以从数字中消除所有 3、6 和 9，以及 0。对于任意数字，您可以按以下方式进行：

• 删除每个 0369
• ，将 47 更改为 1，（因为 4%3 和 7%3 = 1）
• 将58更改为2，原因见上文，
• 将每2更改为11
• ，将每组111更改为空。

如果结果为空，则该数字可以被 3 整除：

echo ${RANDOM}${RANDOM}${RANDOM} | sed 's/[0369]//g;s/[47]/1/g;s/[58]/2/g;s/2/11/g;s/1\{3\}//g'

类似的方法也适用于 9，其中您有类似的规则。但是任意除数的通用方法是什么？