boost xpressive で数列に対する文法を作る
果ては Xpressive みたいな、正規表現を文字列以外の方法で記述できる実装だと、「文字」の「列」ですらなくても「文字とおなじようにふるまうもの」の「列」に対して正規表現使えちゃったりとか。intの配列から、100未満の値が繰り返されてる部分を取り出し！
というお話を聞いて以来ずっと気になっていた boost Xpressive を使ってみる．
お題としては，以前も解いたこの問題，
問題設定はnを1から初めてその２乗を足していき、和が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]
