regex - 0 と 1 の数が等しい正規表現

Question

1 と 0 の数が等しい正規表現を見つける方法。そのような解決策をどのように考えるかにも興味があります。

例: 一致する必要があります: 1100, 00100111 , 01 . 一致すべきではありません: 110 , 0, 11001.

そのようなすべての文字列のセットを与える正規表現が必要です。set の文字列の長さが正規表現で指定された場合2n、 number は number0sと等しくなければなりません1s = n。

Answer 1

通常の文法 (有限状態オートマトン) では不可能: http://en.wikipedia.org/wiki/Regular_language

Answer 2

ニーズを満たす .NET エンジンの正規表現パターンを次に示します。ideone.comで実際の動作をご覧ください。

^((?(D)(?!))(?<C>1)|(?(D)(?!))(?<-C>0)|(?(C)(?!))(?<D>0)|(?(C)(?!))(?<-D>1))*(?(C)(?!))(?(D)(?!))$

2 つのスタックを使用して動作します。現在、0 よりも 1 が多い場合は 1 つ (C) を使用し、1 よりも 0 が多い場合はもう 1 つ (D) を使用します。

きれいではなく、間違いなく使用できませんが、機能します。(はっ！)

Answer 3

1別の回答で述べられているように、これは通常の文法では不可能ですが、文字列をスキャンし、それぞれのカウンターをインクリメントし、それぞれのカウンターをデクリメントするのは比較的簡単なはず0です。最終的なカウントが 0 の場合、0s と1s の数は等しくなります (モジュロ 2^ワードサイズ - オーバーフローに注意すると少し難しくなりますが、入力に関して他に仮定できるかどうかに応じて、必要ないかもしれません）。