正则表达式来定义一些二进制序列

问题描述

你将如何编写一个正则表达式来定义所有 0 和 1 的字符串，作为一个二进制数，代表一个 3 的倍数的整数.

一些有效的二进制数是:

11110100111001111

解决方案

使用 DFA 这里 我们可以用下面的方式做一个正则表达式，其中 A、B、C 代表 DFA 的状态.

A = 1B + 0AB = 1A + 0CC = 1C + 0BC = 1*0B//消除递归B = 1A + 0(1*0B)B = 01*0B + 1AB = (01*0)*1A//消除递归A = 1(01*0)*1A + 0AA = (1(01*0)*1 + 0)AA = (1(01*0)*1 + 0)*//消除递归

导致 PCRE 正则表达式如下:

/^(1(01*0)*1|0)+$/

Perl 测试/示例:

使用严格；对于(qw(111101001110011110110111)){打印 "$_ (", eval "0b$_", ") ";打印/^(1(01*0)*1|0)+$/?匹配":不匹配"；打印\n"；}

输出:

11 (3) 匹配110(6)匹配1001(9)匹配1100(12)匹配1111(15)匹配0 (0) 匹配1 (1) 不匹配10 (2) 不匹配111(7)不匹配

How would you write a regular expression to define all strings of 0's and 1's that, as a binary number, represent an integer that is multiple of 3.

Some valid binary numbers would be:

11
110
1001
1100
1111

解决方案

Using the DFA here we can make a regular expression the following way, where A, B, C represent the states of the DFA.

A = 1B + 0A
B = 1A + 0C
C = 1C + 0B

C = 1*0B // Eliminate recursion

B = 1A + 0(1*0B)
B = 01*0B + 1A
B = (01*0)*1A // Eliminate recursion

A = 1(01*0)*1A + 0A
A = (1(01*0)*1 + 0)A
A = (1(01*0)*1 + 0)* // Eliminate recursion

Resulting in a PCRE regex like:

/^(1(01*0)*1|0)+$/

Perl test/example:

use strict;

for(qw(
11
110
1001
1100
1111
0
1
10
111
)){
    print "$_ (", eval "0b$_", ") ";
    print /^(1(01*0)*1|0)+$/? "matched": "didnt match";
    print "\n";
}

Outputs:

11 (3) matched
110 (6) matched
1001 (9) matched
1100 (12) matched
1111 (15) matched
0 (0) matched
1 (1) didnt match
10 (2) didnt match
111 (7) didnt match

这篇关于正则表达式来定义一些二进制序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！