読者です 読者をやめる 読者になる 読者になる

boost xpressive で数列に対する文法を作る

果ては Xpressive みたいな、正規表現を文字列以外の方法で記述できる実装だと、「文字」の「列」ですらなくても「文字とおなじようにふるまうもの」の「列」に対して正規表現使えちゃったりとか。intの配列から、100未満の値が繰り返されてる部分を取り出し!

というお話を聞いて以来ずっと気になっていた boost Xpressive を使ってみる.
お題としては,以前も解いたこの問題,

問題設定はnを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるかという問題を考えます。

を以下のように置き換える.

与えられた int の数列を調べ,2000 を超えた初めての要素を表示する.そのような要素が無ければ,"not found" と表示する.

regex_match で解く

以下コード.

#include <iostream>
#include <limits>
#include <vector>
#include <boost/xpressive/xpressive.hpp>
#include <boost/xpressive/traits/null_regex_traits.hpp>

void show_answer(std::vector<int> const &vec)
{
    using namespace boost::xpressive;
    typedef basic_regex<std::vector<int>::const_iterator>   iregex;
    typedef match_results<std::vector<int>::const_iterator> imatch;
    null_regex_traits<int> nul;

    iregex rex = imbue(nul)(
           *range(0, 2000)
        >> (s1= range(2001, std::numeric_limits<int>::max()))
        >> *_
    );

    imatch match;
    if(regex_match(vec, match, rex)) {
        std::cout << match[1] << std::endl;
    } else {
        std::cout << "not found" << std::endl;
    }
}

boost 1.35.0 + cl.exe 15.00.21022.08 で動作を確認.
ちなみに Mathematica だとこんな感じになる.

ShowAnswer[{_?(#1 <= 2000 &) ..., x_ /; x > 2000, ___}] := x
ShowAnswer[_] := "not found"

regex_search で解く

regex_match と regex_search で動作が異なる.regex_match は,パターンと数列全体がマッチするかを検証する.regex_search は,数列の部分列がパターンを満たすかどうか検証する.
私の場合,パターンマッチといえば (一方向) 単一化というイメージがあったため,まずは regex_match を選んだ次第だ.念のため regex_search でも書いておく.

void show_answer_ex(std::vector<int> const &vec)
{
    using namespace boost::xpressive;
    null_regex_traits<int> nul;

    iregex rex = imbue(nul)(
        (s1= range(2001, std::numeric_limits<int>::max()))
        );

    imatch match;
    if(regex_search(vec, match, rex)) {
        std::cout << match[1] << std::endl;
    } else {
        std::cout << "not found" << std::endl;
    }
}

regex_token_iterator も試してみる

お題を次のように変更する.

与えられた int の数列を調べ,条件を満たす要素を全て表示する.その条件とは,その要素の直前の要素が偶数であること.

これを regex_token_iterator で解いてみる.

#include <iostream>
#include <limits>
#include <vector>
#include <boost/xpressive/xpressive.hpp>
#include <boost/xpressive/regex_actions.hpp>
#include <boost/xpressive/traits/null_regex_traits.hpp>

typedef boost::xpressive::basic_regex<std::vector<int>::const_iterator>   iregex;
typedef boost::xpressive::match_results<std::vector<int>::const_iterator> imatch;
typedef boost::xpressive::regex_token_iterator<std::vector<int>::const_iterator> iregex_token_iterator;
typedef boost::xpressive::sub_match<std::vector<int>::const_iterator> isub_match;

struct show_impl
{
    typedef void result_type;

    template<typename Value>
    void operator()(Value const &val) const
    {
        std::cout << val << '\t';
    }
};

struct is_even
{
    bool operator()(isub_match const &sub) const
    {
        isub_match::string_type t = sub;
        return t[0] % 2 == 0;
    }
};

void show_answer2(std::vector<int> const &vec)
{
    using namespace boost::xpressive;
    null_regex_traits<int> nul;

    boost::xpressive::function<show_impl>::type const show = {{}};
 
    iregex rex = imbue(nul)(
        after(_ [check(is_even())]) >> _ [show(_)]
    );

    iregex_token_iterator end;

    for(iregex_token_iterator itr(vec.begin(), vec.end(), rex);
        itr != end;
        ++itr )
    {
        std::cout << "move next" << std::endl;
    }
}

例えばこれに,

{1, 5, 14, 30, 55, 91, 140, 204, 285, 385, 506, 650, 819, 1015, 1240, 1496, 1785, 2109, 2470, 2870, 3311, 3795, 4324, 4900, 5525, 6201, 6930, 7714, 8555, 9455}

という数列を喰わせると,

30      move next
55      move next
204     move next
285     move next
650     move next
819     move next
1496    move next
1785    move next
2870    move next
3311    move next
4900    move next
5525    move next
7714    move next
8555    move next

と表示される.
数字の表示にわざわざセマンティックアクションを用いているのは,評価タイミングを示すため.結果はご覧の通り.イテレータを進めるごとに,要素のキャプチャがひとつ進行している.つまりは継続だ.
ついでに Mathematica でも解いてみた.

ShowAnswer2[vec_List] := 
 ReplaceList[vec, {___, _?EvenQ, x_, ___} -> x]