7

文字列内の 0 の数が偶数で、文字列内の 1 の数が偶数であるような正規表現パターンに (任意の長さの) 文字列が一致するかどうかを判断する正規表現を作成しようとしています。このパターンの文字列をチェックするために試して使用できる正規表現ステートメントを決定するのを手伝ってくれる人はいますか?

4

8 に答える 8

8

したがって、すべての変更を反映するように私の答えを完全に再定式化しました。

この正規表現は、0 と 1 のみを含むすべての文字列に一致し、それらが等しい量だけ一致します。

^(?=1*(?:01*01*)*$)(?=0*(?:10*10*)*$).*$

ここでRegexrを参照してください

ここでは、肯定的な先読みアサーションで作業しています。ここでの先読みアサーションの大きな利点は、完全な文字列をチェックするが、それを一致させずにチェックすることです。そのため、両方の先読みは最初から文字列をチェックし始めますが、異なるアサーションを対象としています。

  1. (?=1*(?:01*01*)*$)等しい量の 0 (0 を含む) をチェックします

  2. (?=0*(?:10*10*)*$)等しい量の 1 (0 を含む) をチェックします

  3. .*その後、実際に文字列に一致します

これらの先読みチェック:

(?=
    1*    # match 0 or more 1
    (?:   # open a non capturing group
        0     # match one 0
        1*    # match 0 or more 1
        0     # match one 0
        1*    # match 0 or more 1
    )
    *     # repeat this pattern at least once
    $     # till the end of the string
)
于 2012-04-18T07:39:51.703 に答える
5

だから、私は問題の解決策を考え出しました：

(11+00+(10+01)(11+00)\*(10+01))\*
于 2012-04-26T17:26:53.980 に答える
4

偶数の 0 のセットの場合、次の正規表現を使用して、0 の数が偶数であることを確認できます。

^(1*01*01*)*$

しかし、問題は偶数の 0 と偶数の 1 の両方を持つことだと思います。この問題に対して非決定論的有限オートマトン (NFA) を構築できるため、解は正則であり、正規表現を使用して表すことができます。NFA は以下のマシンを介して表されます。S1 は開始/終了状態です。

S1 ---1----->S2
|^ <--1----- |^
||           ||
00           00
||           ||
v|           v|
S3----1----->S4
  <---1------

そこから、NFA を正規表現に変換する方法がありますが、私の計算コースからしばらく経ちました。以下に、NFA を正規表現に変換するために必要な手順を説明するのに役立つと思われるメモをいくつか示します。

http://www.cs.uiuc.edu/class/sp09/cs373/lectures/lect_08.pdf

于 2012-04-18T07:40:39.333 に答える
1

正規表現ではありませんが（証明することはできませんが、不可能である可能性があります。ポンピング補題による矛盾による証明は失敗します）、「正しい」解決策は、複雑で非効率的な正規表現をすべて一緒に回避し、何かを使用することです。のように（Pythonで）：

def even01(string):
     return string.count("1") % 2 == 0 and string.count("0") % 2 == 0

1または、文字列がsとsのみで構成されている必要がある場合0：

import re
def even01(string):
     return not re.search("[^01]",string) and \
            string.count("1") % 2 == 0 and string.count("0") % 2 == 0
于 2012-04-18T07:56:26.817 に答える
1 
^(0((1(00)*1)*0|1(11|00)*01)|1((0(11)*0)*1|0(11|00)*10))*$

*何も見落としていなければ、これは基本的な正規表現演算子 ( 、^、 )のみを使用して、0 の数が偶数で 1 の数が偶数である任意のビット文字列に一致します$。次のように書くと、どのように機能するかが少しわかりやすくなります。

^(0((1(00)*1)*0
   |1(11|00)*01)
 |1((0(11)*0)*1
   |0(11|00)*10))*$

次のテスト コードは、その正しさを示しています。パターン マッチの結果を、文字列に含まれる 0 と 1 の数が偶数かどうかを示す関数と比較します。長さ 16 のすべてのビット文字列がテストされます。

import re

balanced = lambda s: s.count('0') % 2 == 0 and s.count('1') % 2 == 0

pat = re.compile('^(0((1(00)*1)*0|1(11|00)*01)|1((0(11)*0)*1|0(11|00)*10))*$')

size = 16
num = 2**size
for i in xrange(num):
    binstr = bin(i)[2:].zfill(size)
    b, m = balanced(binstr), bool(pat.match(binstr))
    if b != m:
        print "balanced('%s') = %d, pat.match('%s') = %d" % (binstr, b, binstr, m)
        break
    elif i != 0 and i % (num / 10) == 0:
        # Python 2's `/` operator performs integer division
        print "%d percent done..." % (100 * i / num + 1)
于 2014-05-09T18:47:19.550 に答える
1

再更新

これを試してください: [このデモをチェックしてください: http://regexr.com?30m7c ]

^(00|11|0011|0110|1100|1001)+$

ヒント:

偶数は 2 で割り切れるので、2 進数では常にゼロで終わります ( 0)

于 2012-04-18T07:18:20.633 に答える
0

同じ文 (^ で始まり $ で終わる)内で解決しようとすると、深刻な問題が発生します。:-)

偶数の 0 があることを確認できます ( ^(1*01*01*)*$@david-z が述べたように を使用) 。または、偶数の 1 があることを確認できます。

^(1*01*01*)*$|^(0*10*10*)*$

「00」や「101」など、長さが短い文字列でも機能します。どちらも有効な文字列です。

于 2013-08-31T23:01:19.233 に答える
0

私は空き時間に先読みと先読みにも取り組んでおり、先読みを使用すると、単一の 1 や単一の 0 も考慮しながら問題を解決できます。したがって、式は 11,1111,111111,... および 00,0000,000000,... に対しても機能するはずです。

^(((?=(?:1*01*01*)*$)(?=(?:0*10*10*)*$).*)|([1]{2})*|([0]{2})*)$

すべてのケースで機能します。そのため、文字列が 1 のみまたは 0 のみで構成されている場合:

([1]{2})*|([0]{2})*

0 と 1 が混在している場合は、正の先読みがそれを処理します。

((?=(?:1*01*01*)*$)(?=(?:0*10*10*)*$).*

両方を組み合わせると、偶数の 0 と 1 を持つすべての文字列が考慮されます。

于 2018-07-23T14:15:22.647 に答える