おことわり
ただの C++ 初心者の日記です.
前回,
「初心者が無理しすぎ.もっと段階を分けるべし」
というコメントをいただいたので,考えてみた.
(「調査してみた」等ではなく,「考えてみた」である.なので内容についてはお察しください)
準備
それ以前に,動かしてみるために毎度のように
{ "1", "+", "2", "+", "3" }
みたいな「字句解析済みの状態」な入力値を頑張って書くのが辛くなってきたので,まずはやっつけ仕事で字句解析処理を用意.
また,「サポートする演算子が + オンリー」というのではあまりにも寂しいので,ちょっと追加してみた.
字句解析のやっつけ実装
// std::string_view なる,おしゃれな物があるらしいので,せっかくだから使ってみた.
//(しかし,戻り値に用いるのはどうなのかな? という感はある)
inline std::vector< std::string_view > Tokenize( std::string_view Str )
{
const std::string Elems = "+-*/()?:<>=";
std::vector< std::string_view > Tokens;
size_t iBegin = 0;
for( size_t pos=0; pos<Str.size(); ++pos )
{
if( Elems.find( Str[pos] ) != std::string::npos )
{
if( iBegin < pos )
{
auto range = StrUtil::EraseSpaceAtHeadAndTail( //※先頭と末尾のスペース的な文字を除いた範囲を返す
std::string_view( Str.data()+iBegin, pos-iBegin )
);
if( !range.empty() ){ Tokens.push_back( range ); }
}
if(//{ <=, >=, == } を単一のtokenとする
( Str[pos]=='<' || Str[pos]=='>' || Str[pos]=='=' )
&& ( pos+1<Str.size() )
&& ( Str[pos+1]=='=' )
)
{
Tokens.emplace_back( Str.data()+pos, 2 );
++pos;
}
else
{ Tokens.emplace_back( Str.data()+pos, 1 ); }
iBegin = pos+1;
}
}
if( iBegin < Str.size() )
{
auto range = StrUtil::EraseSpaceAtHeadAndTail(
std::string_view( Str.data()+iBegin, Str.size()-iBegin )
);
if( !range.empty() ){ Tokens.push_back( range ); }
}
return Tokens;
}
構文解析
構文解析処理の結果(何か木構造っぽいやつ)というのは,どんなものになるのか?
わからんが,こんな感じにしてみた.
構文解析の結果用の型
enum class UnaryOP{ Minus };
enum class ArithOP{ Add, Sub, Mul, Div };
enum class CompOP{ L, LE, G, GE, EQ };
enum class TernaryOP{ Cond };
/// <summary>
/// 構文木(?) のノード.
/// 構文解析処理 Parser::Parse() の戻り値用.
/// </summary>
struct TreeNode
{
//末端ノード用
TreeNode( std::string_view token ) : Var( std::string(token) ) {}
//単項演算
TreeNode( UnaryOP op, TreeNode child ) : Var(op)
{ Childs.push_back( std::move(child) ); }
//2項算術演算
TreeNode( ArithOP op, TreeNode lhs, TreeNode rhs ) : Var(op)
{
Childs.push_back( std::move(lhs) );
Childs.push_back( std::move(rhs) );
}
//比較演算
TreeNode( CompOP op, TreeNode lhs, TreeNode rhs ) : Var(op)
{
Childs.push_back( std::move(lhs) );
Childs.push_back( std::move(rhs) );
}
//3項演算
TreeNode( TernaryOP op, TreeNode c1, TreeNode c2, TreeNode c3 ) : Var(op)
{
Childs.push_back( std::move(c1) );
Childs.push_back( std::move(c2) );
Childs.push_back( std::move(c3) );
}
std::variant< std::string, UnaryOP, ArithOP, CompOP, TernaryOP > Var;
std::vector< TreeNode > Childs;
};
で,構文解析処理を上記の TreeNode 型を結果として返す形に変更.
(優先順位毎の関数群の名前がめんどくさくなったので LV1() とか LV2() とかいう名前に…)
構文解析
(横着して, static なメンバ関数しかない class として実装…)
/// <summary>構文解析処理の実装</summary>
class Parser
{
public:
/// <summary>構文解析処理</summary>
/// <param name="Tokens">
/// 字句解析結果.
/// 各要素は前後にスペース(的な文字)を含まない状態であること.
/// 例:{ "1", "+", "25", "*", "(", "36", "-", "14", ")" }
/// </param>
/// <returns>解釈結果.構文木(のルートノード)</returns>
/// <exception cref="invalid_argument">解釈処理に失敗した場合には例外を送出する</exception>
static TreeNode Parse( const std::vector<std::string_view> &Tokens )
{
std::queue< std::string_view > TokenQ;
for( auto &t : Tokens ){ TokenQ.push(t); }
if( auto Result = LV1( TokenQ ); TokenQ.empty() )
{ return Result; }
else
{ throw std::invalid_argument( "Process stopped in the middle (at \"" + std::string(TokenQ.front()) + "\"" ); }
}
private:
Parser() = delete;
/// <summary>解釈作業TOP.(3項演算子)</summary>
/// <param name="Tokens">未解釈のトークン列.この関数内で処理されたトークンは除去される</param>
/// <returns>解釈結果</returns>
/// <exception cref="invalid_argument">解釈処理に失敗した場合には例外を送出する</exception>
static TreeNode LV1( std::queue<std::string_view> &Tokens )
{
auto Result = LV2( Tokens );
//次が "?" なら3項演算子
if( !Tokens.empty() && Tokens.front() == "?" )
{//3項演算子
Tokens.pop(); //"?" を消費
auto Term1 = LV1( Tokens );
if( Tokens.empty() || Tokens.front() != ":" )
{ throw std::invalid_argument( "Missing ':' of CondOP" ); }
Tokens.pop(); //":" を消費
auto Term2 = LV1( Tokens );
return TreeNode( TernaryOP::Cond, std::move(Result), std::move(Term1), std::move(Term2) );
}
else
{ return Result; }
}
private:
/// <summary>解釈作業(比較演算)</summary>
/// <remarks>(引数や戻り値,例外等の仕様は LV1() と同様)</remarks>
static TreeNode LV2( std::queue<std::string_view> &Tokens )
{
auto Result = LV3( Tokens );
while( !Tokens.empty() )
{//<, <=, >, >=, == を処理
auto token = Tokens.front();
if( token=="<" )
{
Tokens.pop();
Result = TreeNode( CompOP::L, std::move(Result), LV3(Tokens) );
}
else if( token=="<=" )
{
Tokens.pop();
Result = TreeNode( CompOP::LE, std::move(Result), LV3(Tokens) );
}
else if( token==">" )
{
Tokens.pop();
Result = TreeNode( CompOP::G, std::move(Result), LV3(Tokens) );
}
else if( token==">=" )
{
Tokens.pop();
Result = TreeNode( CompOP::GE, std::move(Result), LV3(Tokens) );
}
else if( token=="==" )
{
Tokens.pop();
Result = TreeNode( CompOP::EQ, std::move(Result), LV3(Tokens) );
}
else
{ break; }
}
return Result;
}
/// <summary>解釈作業(2項 +,-)</summary>
/// <remarks>(引数や戻り値,例外等の仕様は LV1() と同様)</remarks>
static TreeNode LV3( std::queue<std::string_view> &Tokens )
{
auto Result = LV4( Tokens );
while( !Tokens.empty() )
{//2項 +, - を処理
auto token = Tokens.front();
if( token=="+" )
{
Tokens.pop();
Result = TreeNode( ArithOP::Add, std::move(Result), LV4(Tokens) );
}
else if( token=="-" )
{
Tokens.pop();
Result = TreeNode( ArithOP::Sub, std::move(Result), LV4(Tokens) );
}
else
{ break; }
}
return Result;
}
/// <summary>解釈作業(2項 *,/)</summary>
/// <remarks>(引数や戻り値,例外等の仕様は LV1() と同様)</remarks>
static TreeNode LV4( std::queue<std::string_view> &Tokens )
{
auto Result = LV5( Tokens );
while( !Tokens.empty() )
{//*, / を処理
auto token = Tokens.front();
if( token=="*" )
{
Tokens.pop();
Result = TreeNode( ArithOP::Mul, std::move(Result), LV5(Tokens) );
}
else if( token=="/" )
{
Tokens.pop();
Result = TreeNode( ArithOP::Div, std::move(Result), LV5(Tokens) );
}
else
{ break; }
}
return Result;
}
/// <summary>解釈作業(単項マイナス, 括弧)</summary>
/// <remarks>(引数や戻り値,例外等の仕様は LV1() と同様)</remarks>
static TreeNode LV5( std::queue<std::string_view> &Tokens )
{
if( Tokens.empty() )
{ throw std::invalid_argument( "(LV5)Missing Token" ); }
if( Tokens.front() == "-" )
{//単項 - を処理
Tokens.pop();
return TreeNode( UnaryOP::Minus, LV5(Tokens) );
}
else if( Tokens.front() == "(" )
{//() を処理
Tokens.pop(); // '(' を消費
auto InnerExp = LV1( Tokens );
if( Tokens.empty() || Tokens.front() != ")" )
{ throw std::invalid_argument( "Missing ')'" ); }
Tokens.pop(); // ')' を消費
return InnerExp;
}
else
{ return LV6( Tokens ); }
}
/// <summary>解釈作業(直値,変数等)</summary>
/// <remarks>(引数や戻り値,例外等の仕様は LV1() と同様)</remarks>
static TreeNode LV6( std::queue<std::string_view> &Tokens )
{
if( Tokens.empty() )
{ throw std::invalid_argument( "(LV6)Missing Token" ); }
std::string_view token = Tokens.front();
Tokens.pop();
return TreeNode( token );
}
};
どうやって評価するのか
上記が相応に動くのだと仮定して……
「で,どうやって評価する(計算させる)の?」っていう.
(1) 構文解析の結果から直接評価
とりあえず,「 TreeNode を入力として→ダイレクトに計算する」というやり方を書いてみた.
これだと計算毎に毎回,分岐とか文字列を数値に変換する処理だとかが走るので,良ろしくない……と思う.
ダイレクトに計算
- 数値の型は何なのか?
int?double?
→Val_tなる template 型引数にした. - シンボルの評価手段をどう入れ込むのか?
→ (別にそうすべき理由があるわけじゃないけども,興味本位で) CRTP なる形に書いてみた.
/// <summary>評価処理手段</summary>
/// <typeparam name="Val_t">演算結果値の型(数値型を想定)</typeparam>
/// <typeparam name="Deriv_t">派生クラスの型(CRTP)</typeparam>
template< typename Val_t, class Deriv_t >
class EvaluatorBase
{
public:
/// <summary>評価処理</summary>
/// <param name="Node">評価対象構文木(のルートノード)</param>
/// <returns>評価結果値</returns>
Val_t Evaluate( const TreeNode &Node ) const
{
return std::visit(
[this, &Childs=Node.Childs]( const auto &v )->Val_t{ return this->Eval( v, Childs ); },
Node.Var
);
}
private:
Val_t Eval( const std::string &Token, const std::vector<TreeNode> & ) const
{
//※CvtStr2T<Val_t>() は文字列を Val_t 値に解釈する処理.
//(戻り値は optional<Val_t> で,解釈失敗時には nullopt )
if( auto val = StrUtil::CvtStr2T<Val_t>( Token ); val )
{ return val.value(); }
else
{ return Deriv().Eval_Symbol( Token ); }
}
Val_t Eval( const UnaryOP &OP, const std::vector<TreeNode> &Childs ) const
{
if( OP == UnaryOP::Minus ){ return -Evaluate( Childs[0] ); }
throw std::invalid_argument( "Invalid OP" );
}
Val_t Eval( const ArithOP &OP, const std::vector<TreeNode> &Childs ) const
{
switch( OP )
{
case ArithOP::Add: return Evaluate(Childs[0]) + Evaluate(Childs[1]);
case ArithOP::Sub: return Evaluate(Childs[0]) - Evaluate(Childs[1]);
case ArithOP::Mul: return Evaluate(Childs[0]) * Evaluate(Childs[1]);
case ArithOP::Div: return Evaluate(Childs[0]) / Evaluate(Childs[1]);
default: throw std::invalid_argument( "Invalid OP" );
}
}
Val_t Eval( const CompOP &OP, const std::vector<TreeNode> &Childs ) const
{
switch( OP )
{
case CompOP::L: return static_cast<Val_t>( Evaluate(Childs[0]) < Evaluate(Childs[1]) );
case CompOP::LE: return static_cast<Val_t>( Evaluate(Childs[0]) <= Evaluate(Childs[1]) );
case CompOP::G: return static_cast<Val_t>( Evaluate(Childs[0]) > Evaluate(Childs[1]) );
case CompOP::GE: return static_cast<Val_t>( Evaluate(Childs[0]) >= Evaluate(Childs[1]) );
case CompOP::EQ: return static_cast<Val_t>( Evaluate(Childs[0]) == Evaluate(Childs[1]) );
default: throw std::invalid_argument( "Invalid OP" );
}
}
Val_t Eval( const TernaryOP &OP, const std::vector<TreeNode> &Childs ) const
{
if( OP == TernaryOP::Cond )
{ return ( static_cast<bool>( Evaluate(Childs[0]) ) ? Evaluate(Childs[1]) : Evaluate(Childs[2]) ); }
throw std::invalid_argument( "Invalid OP" );
}
const Deriv_t &Deriv() const { return *static_cast<const Deriv_t*>(this); }
protected: //派生クラスで実装を変えられる部分
// 変数(や定数)名への対応用
Val_t Eval_Symbol( const std::string &Symbol ) const
{ throw std::invalid_argument( "Invalid Symbol : \"" + Symbol + "\"" ); }
};
(2) 関数を作る
前回の日記と同じ形に持ち込む,というやり方.
元の木阿弥(?) という感じがしないでもないが…?
std::function を作る
- シンボルの評価手段をどう入れ込むのか?
→ 処理者の ctor に渡す,という形に書いてみた.
/// <summary>
/// 演算処理手段 : operator() で Val_t 型の演算結果値を取得できるもの
/// </summary>
/// <typeparam name="Val_t">演算結果値の型(何らかの数値型)</typeparam>
/// <typeparam name="...CTXTS">
/// operator()の引数用の型.
/// (想定:変数や定数の名称みたいなのを扱うための何か)
/// </typeparam>
template< typename Val_t, typename ...CTXTS >
using EvalFunc = std::function< Val_t( const CTXTS &... ) >;
/// <summary>構文解析結果 -> 演算処理手段</summary>
template< typename Val_t, typename ...CTXTS >
class Builder
{
public:
/// <summary>
/// 引数に与えられた文字列を変数(や定数)として解釈する手段.
/// 戻り値は,変数(定数)値を返す関数.
/// ただし,引数が妥当に解釈できないものであった場合には nullptr を返す.
/// </summary>
using SymbolParseFunc = std::function< EvalFunc<Val_t,CTXTS...>( const std::string & ) >;
public:
/// <summary>ctor</summary>
/// <param name="SPF">変数(や定数)を処理するための手段</param>
Builder( SymbolParseFunc SPF = nullptr ) : m_SPF( std::move(SPF) ) {}
private:
SymbolParseFunc m_SPF;
public:
/// <summary>演算手段生成処理</summary>
/// <param name="Node">評価対象構文木(のルートノード)</param>
/// <returns>演算手段</returns>
/// <exception cref="invalid_argument">処理に失敗した場合には例外を送出する</exception>
EvalFunc<Val_t,CTXTS...> Build( const TreeNode &RootNode ) const
{
return std::visit(
[ this, &Childs=RootNode.Childs ]( const auto &v ){ return this->Build_Part( v, Childs ); },
RootNode.Var
);
}
private:
EvalFunc<Val_t,CTXTS...> Build_Part( const std::string &Token, const std::vector<TreeNode> & ) const
{
if( auto val_ = StrUtil::CvtStr2T<Val_t>( Token ); val_ )
{ return [ v=val_.value() ]( const CTXTS &... ){ return v; }; }
if( m_SPF )
{
if( auto f = m_SPF( Token ); f )
{ return f; }
}
//ERR:未知の文字列
throw std::invalid_argument( "Invalid Token : \"" + std::string(Token) + "\"" );
}
EvalFunc<Val_t,CTXTS...> Build_Part( const UnaryOP &OP, const std::vector<TreeNode> &Childs ) const
{
if( OP == UnaryOP::Minus )
{ return [f=Build(Childs[0])]( const CTXTS &... Ctxts ){ return -f(Ctxts...); }; }
throw std::invalid_argument( "Invalid OP" );
}
EvalFunc<Val_t,CTXTS...> Build_Part( const ArithOP &OP, const std::vector<TreeNode> &Childs ) const
{
switch( OP )
{
case ArithOP::Add:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return lhs(Ctxts...) + rhs(Ctxts...); };
case ArithOP::Sub:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return lhs(Ctxts...) - rhs(Ctxts...); };
case ArithOP::Mul:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return lhs(Ctxts...) * rhs(Ctxts...); };
case ArithOP::Div:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return lhs(Ctxts...) / rhs(Ctxts...); };
default: throw std::invalid_argument( "Invalid OP" );
}
}
EvalFunc<Val_t,CTXTS...> Build_Part( const CompOP &OP, const std::vector<TreeNode> &Childs ) const
{
switch( OP )
{
case CompOP::L:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return static_cast<Val_t>( lhs(Ctxts...) < rhs(Ctxts...) ); };
case CompOP::LE:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return static_cast<Val_t>( lhs(Ctxts...) <= rhs(Ctxts...) ); };
case CompOP::G:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return static_cast<Val_t>( lhs(Ctxts...) > rhs(Ctxts...) ); };
case CompOP::GE:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return static_cast<Val_t>( lhs(Ctxts...) >= rhs(Ctxts...) ); };
case CompOP::EQ:
return [ lhs=Build(Childs[0]), rhs=Build(Childs[1]) ]( const CTXTS &... Ctxts ){ return static_cast<Val_t>( lhs(Ctxts...) == rhs(Ctxts...) ); };
default:
throw std::invalid_argument( "Invalid OP" );
}
}
EvalFunc<Val_t,CTXTS...> Build_Part( const TernaryOP &OP, const std::vector<TreeNode> &Childs ) const
{
if( OP == TernaryOP::Cond )
{
return
[ cond=Build(Childs[0]), t1=Build(Childs[1]), t2=Build(Childs[2]) ](const CTXTS &... Ctxts)
{ return ( static_cast<bool>( cond(Ctxts...) ) ? t1(Ctxts...) : t2(Ctxts...) ); };
}
throw std::invalid_argument( "Invalid OP" );
}
};
しかし "1+3" に対して,律儀に「 1+3 を計算してその結果を返す手段(function)」というのを返すというのも馬鹿っぽいというかなんというか……
そこはせめて「 4 を返す手段」にまとめておこうぜ的な気がする.
すなわち, 直値 op 直値 みたいな形のはその場で計算して結果を保持しようよ的な.
(「各2項演算に4パターンの分岐を書く」ことになりそうでとても面倒そうだからパス……)
動かしてみるてすと
namespace
{
//評価時引数用の型
struct MyCtxt
{
MyCtxt() : m_mt( std::random_device{}() ) {}
int Dice( int nFace ) const { return std::uniform_int_distribution<int>(1,nFace)( m_mt ); }
static EvalFunc<int,MyCtxt> ParseSymbol( const std::string &Token )
{
if( Token=="Cat" ){ return []( const MyCtxt &C ){ return C.Cat; }; }
if( Token=="Nap" ){ return []( const MyCtxt &C ){ return C.Nap; }; }
if( Token=="Meow" ){ return []( const MyCtxt &C ){ return C.Meow; }; }
if( Token.size()>=2 && Token[0]=='D' )
{//サイコロが振れるよ!
if( int nFace = std::atoi( Token.substr(1).c_str() ); nFace>=2 )
{ return [nFace]( const MyCtxt &C ){ return C.Dice(nFace); }; }
}
return nullptr;
}
private: //※評価処理中にうっかりコピーとか作られてないことを確認
MyCtxt( const MyCtxt & ) = delete;
MyCtxt &operator=( const MyCtxt & ) = delete;
private:
int Cat = 2;
int Nap = 5;
int Meow = 40;
mutable std::mt19937 m_mt;
};
//テスト
void Test( std::string_view ExpressionStr )
{
std::cout << "\"" << ExpressionStr << "\" -> ";
auto Tokens = Tokenize( ExpressionStr );
if( !Tokens.empty() )
{
std::cout << "|";
for( auto t : Tokens ){ std::cout << t << "|"; }
}
else
{ std::cout << "(No Tokens)"; }
std::cout << "\n\t-> ";
try
{
auto TreeHead = Parser::Parse(Tokens);
auto EvalFunc = Builder<int,MyCtxt>( MyCtxt::ParseSymbol ).Build( TreeHead );
std::cout << EvalFunc( MyCtxt() ) << "\n";
}
catch( std::invalid_argument &ex )
{ std::cout << ex.what() << "\n"; }
}
}
int main()
{//いろんな文字列を与えてみる
Test( "" );
Test( "D6+100+D6" );
Test( " 5 " );
Test( " -Meow / 10+1" );
Test( "--( Cat>1000 ? 1+3 : Nap*(5+5) )" );
Test( "Cat==2?0:9?20:6" );
Test( "(Cat==2?0:9)?20:6" );
Test( "3.14" );
Test( "1--2" );
Test( " + 6" );
Test( " 4 * Kitten" );
}
出力:
エラー時の文言が分かりにくい(というか,どのタイミングでエラーになるべきか?というのがイマイチちゃんとしてない)気がするが,一応失敗にはなっている.
"" -> (No Tokens)
-> (LV5)Missing Token
"D6+100+D6" -> |D6|+|100|+|D6|
-> 105
" 5 " -> |5|
-> 5
" -Meow / 10+1" -> |-|Meow|/|10|+|1|
-> -3
"--( Cat>1000 ? 1+3 : Nap*(5+5) )" -> |-|-|(|Cat|>|1000|?|1|+|3|:|Nap|*|(|5|+|5|)|)|
-> 50
"Cat==2?0:9?20:6" -> |Cat|==|2|?|0|:|9|?|20|:|6|
-> 0
"(Cat==2?0:9)?20:6" -> |(|Cat|==|2|?|0|:|9|)|?|20|:|6|
-> 6
"3.14" -> |3.14|
-> Invalid Token : "3.14"
"1--2" -> |1|-|-|2|
-> 3
" + 6" -> |+|6|
-> Process stopped in the middle (at "6")
" 4 * Kitten" -> |4|*|Kitten|
-> Invalid Token : "Kitten"
まとめ(?)
(未定)
- C++の練習の題材としては結構いいんじゃないかな.
わりといろんな事柄を(わざわざ? あえて?)使ってみる機会みたいなのがあるし,動くとそれなりに「おー,動いた」みたいな感じがある.