Rubyの正規表現で加算を判定する
正規表現における「再帰」をご存知でしょうか。一部の正規(自称)表現では再帰的なパターンを定義できるような拡張がなされており、Rubyが使っているOnigmoの正規表現でも再帰の機能が利用できます。この機能は「田中哲スペシャル」と呼ばれて多くの人に愛されているはずなのですが、なぜか2進数の処理に関する記述がググっても見つからなかったので、ここで2進数(と10進数)の足し算について書きたいと思います。
環境: Ruby 2.4.2; (?~)は使ってないから2.3以下でもたぶん動く
- 11/25 0:00 10進数の足し算を追記
- 11/26 22:10 TSGの今年の部報へのリンクを追加
- 12/10 11:00 桁数が違う場合の記事へのリンクを追加
前提
正規表現or正規表現の再帰をご存知ない方は、TSGの昨年の部報のid:moratorium08さんの記事(p.5)や、今年の部報の私の記事(p.17)をご参照ください。
Perlの正規表現をご存知なら、Perlの\k{name}や\g{name}がRubyでは\k<name>に、またPerlの(?&name)や(?P>name)が\g<name>になっていると思ってください。
Perlの正規表現はとても強力で任意のPerlコードを直接埋め込めるので、
m/^([01]++)\+([01]++)=0*(??{ sprintf "%b", oct("0b".$1) + oct("0b".$2) })$/
と書くことで"0+0=0"や"10+11=101"にマッチする2進数加算判定の正規表現を作ることができます。
一方Rubyの正規表現はそこまで強力ではありません。しかし再帰を使えば、2進数の加算程度なら書くことができます。
本題
ADD = / # A + B = C (?<B0> (?= (?<B0Rec> [01] \g<B0Rec> [01] | \+ .*? 0 ) \= )){0} (?<B1> (?= (?<B1Rec> [01] \g<B1Rec> [01] | \+ .*? 1 ) \= )){0} (?<C0> (?= (?<C0Rec> [01] \g<C0Rec> [01] | \+ .*? 0 ) $ )){0} (?<C1> (?= (?<C1Rec> [01] \g<C1Rec> [01] | \+ .*? 1 ) $ )){0} (?<Carry0> (?= (?: 1 \g<B0> | 0 \g<B1> )*+ (?: 0 \g<B0> | \+ ))){0} (?<Carry1> (?= (?: 1 \g<B0> | 0 \g<B1> )*+ 1 \g<B1> )){0} ^ \g<Carry0> (?: 0 \g<B0> \g<Carry0> \g<C0> | 0 \g<B0> \g<Carry1> \g<C1> | 0 \g<B1> \g<Carry0> \g<C1> | 0 \g<B1> \g<Carry1> \g<C0> | 1 \g<B0> \g<Carry0> \g<C1> | 1 \g<B0> \g<Carry1> \g<C0> | 1 \g<B1> \g<Carry0> \g<C0> | 1 \g<B1> \g<Carry1> \g<C1> )++ \+ [01]++ \= [01]++ $ /x
これは、入力が"A+B=C"(A,B,Cは全て同じ桁数の2進数)という形式で与えられることを前提として*2、実際に になっているときだけマッチする正規表現です。
最初に色々なパターンの定義が入っています。{0}をつけることによってこの時点ではマッチングは行われず、ただ単に後々参照するものを先にまとめて定義しただけになります(参考: プログラミング/ruby/正規表現 - 武内＠筑波大)。
同じ位置の桁
(?<B0>),(?<B1>),(?<C0>),(?<C1>)はどれも、Aの 桁目(以降
)を読み終えたところからスタートしてB,Cの同じ桁、つまり
や
を参照するテクニックを用いています。このテクは部報の「補数」の節にも書きましたがもう一度説明します。
(?<Rec> X \g<Rec> Y | ZZZ )という再帰的なパターンは、"XX…XXZZZYY…YY"という形式の文字列にマッチし、このときXとYの数は等しくなることがわかります。
具体的に(?<Bp>)( )を考えます。Xの直後に
"+"が来ることから、Xは から
(ただし
はAの長さ)の
文字です。Yも等しく
文字あり、また︎Yの直後に
"="が来ることより、︎Yは から
だとわかります。従ってZの右端は
になります。これが
に等しいときマッチします。
繰り上がり
1繰り上がって来る桁は、どこかに1+1という桁(起点)が存在して、その起点から左(上位)に0個以上の1+0(+繰り上がり1)を挟んだところにある桁です。
何の捻りもなく、 や
を0個以上読み、その先に起点
があるかどうかを
(?<Bp>)も利用して判定しています。
足し算の判定
、
、繰り上がりの計3つのパラメータがそれぞれ0か1を取るときの
の値を判定すればいいので、
個のパターンを書いて完成です。
まとめ
この方法を用いると当然10進法の加算もできるのですが、通りのパターンを書く部分が煩雑になるのでいい方法がないかなーと悩んでいます。
追記(11/25 0:00) 書きました: add10.rb - Gist
また、部報に書いた通り毎回繰り上がりを判定するのではなく下の位から順に繰り上がりを保持しながら判定していくというのもやってみたいです。良い方法があれば教えてください。
A,B,Cが同じ桁数じゃない場合の処理もすぐ書けそうなので書けたら追記します。
追記(12/10 11:00) 書きました: Rubyの正規表現で足し算 (2) 異なる桁数 - Lを探す日常
宣伝: 今回何度も登場(し|させ)た部報は2017年駒場祭号ですが、まさに現在(2017/11/24-11/26)東大駒場キャンパスにて駒場祭が開催中です！ TSGも出展していますので是非ご来場ください*3！
それでは、皆さんもよい正規表現ライフを過ごしてください。
