Lを探す日常

競プロ、ゴルフとか

Rubyの正規表現で足し算 (2) 異なる桁数

この記事はTSG Advent Calendar 2017の10日目です。昨日の記事は id:gasin さんの[null]でした。TSGでは(特に1年生の)新入部員を募集しています。

さて、TSGの先輩方と雑談しているときに出てきた「正規表現で2進数を扱ったりして遊ぶ」という話題を発展させて、正規表現で足し算の式が正しいか判定することについて考えます。
先日の記事「Rubyの正規表現で加算を判定する (1)」では次のようなRuby正規表現を書きました:

ADD2 =~ "1+0=1"
ADD2 =~ "011+001=100"
ADD2 !~ "1+1=0"

ADD10 =~ "1+1=2"
ADD10 =~ "486+001=487"
ADD10 !~ "123+456=789"

二進、十進それぞれ2番目の例において、数の先頭に余分な0が付いています。これは前回紹介した正規表現に「A,B,Cは全て同じ桁数」という制約があったためです。
今回の目標は、この不自然な制約を、「数の先頭に余分な0が付いていない*1」という(自然な)制約に変えて*2自然な形式の足し算を判定する正規表現を作ることです。

※完成したものはGistにあります

*1:非零の数は「1」から始まる

*2:逆に01+01=10のような文字列は受け付けない

続きを読む

Rubyの正規表現で加算を判定する

正規表現における「再帰」をご存知でしょうか。一部の正規(自称)表現では再帰的なパターンを定義できるような拡張がなされており、Rubyが使っているOnigmoの正規表現でも再帰の機能が利用できます。この機能は「田中哲スペシャル」と呼ばれて多くの人に愛されているはずなのですが、なぜか2進数の処理に関する記述がググっても見つからなかったので、ここで2進数(と10進数)の足し算について書きたいと思います。

続きを読む