0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@NyancoRitter

数式の構文解析なんかうまく書けない

0
Last updated at Posted at 2026-03-24

おことわり

ただの C++ 初心者の日記です．

話

なぜか突然，数式な文字列から計算するやつを作ってみようと思った．
例えば 1+2+3 という文字列を与えると 6 が得られるようなやつだ．

まずは

  • 扱える値は整数
  • 演算子は（２項演算の） + だけ

という簡素なやつを書いてみた．

namespace
{
	//文字列を整数に解釈する作業
	inline std::optional<long> StrToLong( const std::string &Str )
	{
		if( Str.empty() )return std::nullopt;
		char *endptr = nullptr;
		auto val = std::strtol( Str.c_str(), &endptr, 0 );
		if( *endptr == '\0' ){	return val;	}
		else{	return std::nullopt;	}
	}
}

namespace Ex1
{
    //（構文解析処理の戻り値の型）
	//計算結果が整数(int)になる関数
	using EvalFunc = std::function<int(void)>;

	namespace Impl
	{
		std::pair< EvalFunc, size_t > Parse_Value( const std::vector<std::string> &Tokens, size_t idx )
		{
			if( idx >= Tokens.size() ){	throw std::invalid_argument( "invalid index : " + std::to_string(idx) );	}
			if( auto value_ = StrToLong( Tokens[idx] );	value_ )
			{
				auto val = value_.value();
				return { [val](){	return val;	},	idx+1	};
			}
			else
			{	throw std::invalid_argument( "invalid token : " + Tokens[idx] );	}
		}

		std::pair< EvalFunc, size_t > Parse_Plus( const std::vector<std::string> &Tokens, size_t idx )
		{
			if( idx >= Tokens.size() ){	throw std::invalid_argument( "invalid index : " + std::to_string(idx) );	}
			auto Result = Parse_Value( Tokens, idx );
			while( Result.second < Tokens.size() )
			{
				const auto &NextToken = Tokens[ Result.second ];
				if( NextToken == "+" )
				{
					auto Rhs = Parse_Value( Tokens, Result.second+1 );
					Result.first = [lhs=std::move(Result.first), rhs=std::move(Rhs.first)](){	return ( lhs() + rhs() );	};
					Result.second = Rhs.second;
				}
				else
				{	break;	}
			}
			return Result;
		}
	}

	//構文解析処理．成功時には計算手段を返す
	EvalFunc Parse_Exp( const std::vector<std::string> &Tokens )
	{
		if( auto Result = Impl::Parse_Plus(Tokens,0);	Result.second >= Tokens.size() )
		{	return Result.first;	}
		else
		{	throw std::invalid_argument( "process stopped in the middle" );	}
	}
}

"1+2+3" みたいな文字列を { "1", "+", "2", "+", "3" } に分解する処理（「字句解析」とか呼ぶのかな）は別途あるのだとして……
std::cout << Parse_Exp( { "1", "+", "2", "+", "3" } )(); とか呼ぶと 6 と出力されれば成功，という話だ．
多分動く感．OK.

変数/定数 みたいなの

上記だと項は 1 とか 2 みたいな数値丸出しなやつしか扱えない．
x とか y とか Cat みたいな項も扱いたい気がする．x+4+Cat とか書きたいのである．

解決すべき課題は下記２点か：

  • 解決すべき課題(1)：構文解析時に x とか Cat とかいう文字列が妥当なシンボル名称であるか否かを判定する必要がある（未知の文字列だったらエラーにする）
  • 解決すべき課題(2)：計算時に「 x やらの現在の値っていうのはいくつなんですかね？」というのを解決できる必要がある

とりあえず(2)に関して考えると
「なんかわからんけど，そこらへんをどうにかして解決してくれるやつの型」というが存在するのだということにして，計算時にそれを引数に受ければいいかな．
この型を template 型引数にするとしたら，構文解析処理の戻り値の型というのは

//計算結果が整数(int)になる関数．
//Ctxt_t は「そこらへんをどうにかして解決してくれるやつ」の型であり，計算時に引数として与えられる．
template< typename Ctxt_t >
using EvalFunc = std::function<int(const Ctxt_t &)>;

みたいな？

あ，でも「別にそういうのがいらない（：数値丸出しなやつだけが扱えればOKという）場面」でも使えるようにしたい…気がする．
すなわち，この Ctxt_t というのが void である場合にもどうにかこうにかしたい．
そしたら……

//
//void に関しては引数が無い形に特殊化する
//

template< typename Ctxt_t >
struct Eval{	using Func = std::function< int(const Ctxt_t &) >;	};

template<>
struct Eval<void>{	using Func = std::function< int() >;	};

//計算結果が整数(int)になる関数．
//Ctxt_t が void の場合には引数無し．
template< typename Ctxt_t >
using EvalFunc = typename Eval<Ctxt_t>::Func;

とかかな？
それじゃ先ほど実装した関数群も template< typename Ctxt_t > な関数テンプレートに変更してみる．

namespace Ex2
{
	template< typename Ctxt_t >
	struct Eval{	using Func = std::function< int(const Ctxt_t &) >;	};

	template<>
	struct Eval<void>{	using Func = std::function< int() >;	};

	template< typename Ctxt_t >
	using EvalFunc = typename Eval<Ctxt_t>::Func;

	//シンボル文字列に対する値（変数名に対する変数値みたいな）を得る手段を返す．
	//ただし，無理な場合（不正な文字列に対して）は nullptr を返す．
	template< typename Ctxt_t >
	EvalFunc<Ctxt_t> Parse_Symbol( const std::string &Token ){	return nullptr;	}

	namespace Impl
	{
		template< typename Ctxt_t >
		std::pair< EvalFunc<Ctxt_t>, size_t > Parse_Value( const std::vector<std::string> &Tokens, size_t idx )
		{
			if( idx >= Tokens.size() ){	throw std::invalid_argument( "invalid index : " + std::to_string(idx) );	}
			if( auto value_ = StrToLong( Tokens[idx] );	value_ )
			{
				auto val = value_.value();
				if constexpr( std::is_void_v<Ctxt_t> )  //うまく実装できない感
				{	return { [val](){	return val;	},	idx+1	};	}
				else
				{	return { [val](const Ctxt_t &){	return val;	},	idx+1	};	}
			}
			else if( auto F = Parse_Symbol<Ctxt_t>( Tokens[idx] );	F )
			{	return { F, idx+1 };	}
			else
			{	throw std::invalid_argument( "invalid token : " + Tokens[idx] );	}
		}

		template< typename Ctxt_t >
		std::pair< EvalFunc<Ctxt_t>, size_t > Parse_Plus( const std::vector<std::string> &Tokens, size_t idx )
		{
			if( idx >= Tokens.size() ){	throw std::invalid_argument( "invalid index : " + std::to_string(idx) );	}
			auto Result = Parse_Value<Ctxt_t>( Tokens, idx );
			while( Result.second < Tokens.size() )
			{
				const auto &NextToken = Tokens[ Result.second ];
				if( NextToken == "+" )
				{
					auto Rhs = Parse_Value<Ctxt_t>( Tokens, Result.second+1 );
					if constexpr( std::is_void_v<Ctxt_t> )  //うまく実装できない感
					{
						Result.first = [lhs=std::move(Result.first), rhs=std::move(Rhs.first)](){	return ( lhs() + rhs() );	};
					}
					else
					{
						Result.first = [lhs=std::move(Result.first), rhs=std::move(Rhs.first)](const Ctxt_t & Ctxt){	return ( lhs(Ctxt) + rhs(Ctxt) );	};
					}
					Result.second = Rhs.second;
				}
				else
				{	break;	}
			}
			return Result;
		}
	}

	template< typename Ctxt_t=void >
	EvalFunc<Ctxt_t> Parse_Exp( const std::vector<std::string> &Tokens )
	{
		if( auto Result = Impl::Parse_Plus<Ctxt_t>(Tokens,0);	Result.second >= Tokens.size() )
		{	return Result.first;	}
		else
		{	throw std::invalid_argument( "process stopped in the middle" );	}
	}
}
  • 解決すべき課題(1)：構文解析時に x とか Cat とかいう文字列が妥当なシンボル名称であるか否かを判定する必要がある

に関しては， Parse_Symbol() なる関数テンプレートの特殊化を利用者側で用意して対処する……ということで．

（やってみるTest） 
struct CatCtxt
{
	int Meow = 0;
	int Nap = 0;
};

template<>
Ex2::EvalFunc<CatCtxt> Ex2::Parse_Symbol<CatCtxt>( const std::string &Token )
{
	if( Token == "Meow" ){	return []( const CatCtxt &Ctxt ){	return Ctxt.Meow;	};	}
	if( Token == "Nap" ){	return []( const CatCtxt &Ctxt ){	return Ctxt.Nap;	};	}
	return nullptr;
}

void Test()
{//993 と出力されれば成功
	CatCtxt Ctxt;
	Ctxt.Meow = -10;
	Ctxt.Nap = 1000;
	try
	{
		std::cout << Ex2::Parse_Exp<CatCtxt>( { "3", "+", "Meow", "+", "Nap" } )( Ctxt ) << std::endl;
	}
	catch( std::invalid_argument &ex )
	{	std::cout << ex.what() << std::endl;	}
}

しかし if constexpr( std::is_void_v<Ctxt_t> ) というのが複数個所に毎度のように現れる形になってしまったのが何かすっきりしないというか……イマイチ感．
もっとうまい書き方(?)は無いのであろうか？
これだとサポートする演算子（ - とか * とか）を増やそうとかするごとに毎回こんな形のを書く必要が生じるよねこれ．うーむ．

Impl内の関数の引数はqueueの方が見た目すっきりするかも

index値を渡したり受けたりするよりも，消費したトークンを都度捨てていく形の方がわかりやすい気がする．

引数をqueueに 
namespace Impl
{
	template< typename Ctxt_t >
	EvalFunc<Ctxt_t> Parse_Value( std::queue<std::string> &Tokens )
	{
		if( Tokens.empty() ){	throw std::invalid_argument( "Empty!" );	}

		auto token = Tokens.front();
		Tokens.pop();
		if( auto value_ = StrToLong( token );	value_ )
		{
			auto val = value_.value();
			if constexpr( std::is_void_v<Ctxt_t> )
			{	return [val](){	return val;	};	}
			else
			{	return [val](const Ctxt_t &){	return val;	};	}
		}
		else if( auto F = Parse_Symbol<Ctxt_t>( token );	F )
		{	return F;	}
		else
		{	throw std::invalid_argument( "invalid token : " + token );	}
	}

	template< typename Ctxt_t >
	EvalFunc<Ctxt_t> Parse_Plus( std::queue<std::string> &Tokens )
	{
		if( Tokens.empty() ){	throw std::invalid_argument( "Empty!" );	}
		auto Result = Parse_Value<Ctxt_t>( Tokens );
		while( !Tokens.empty() )
		{
			if( Tokens.front() == "+" )
			{
				Tokens.pop();
				auto Rhs = Parse_Value<Ctxt_t>( Tokens );
				if constexpr( std::is_void_v<Ctxt_t> )
				{
					Result = [lhs=std::move(Result), rhs=std::move(Rhs)](){	return ( lhs() + rhs() );	};
				}
				else
				{
					Result = [lhs=std::move(Result), rhs=std::move(Rhs)](const Ctxt_t & Ctxt){	return ( lhs(Ctxt) + rhs(Ctxt) );	};
				}
			}
			else
			{	break;	}
		}
		return Result;
	}
}

template< typename Ctxt_t=void >
EvalFunc<Ctxt_t> Parse_Exp( const std::vector<std::string> &Tokens )
{
    //ここで一旦キューに詰めなおすというのが若干ダサい感……？
	std::queue<std::string> TokenQ;
	for( const auto &token : Tokens ){	TokenQ.push( token );	}

	if( auto Result = Impl::Parse_Plus<Ctxt_t>(TokenQ);	TokenQ.empty() )
	{	return Result;	}
	else
	{	throw std::invalid_argument( "process stopped in the middle" );	}
}

こうじゃねーの？

if constexpr( std::is_void_v<Ctxt_t> ) というのが複数個所に…

「２項演算の関数を作り出す関数テンプレート」みたいなのを用意して，各２項演算 { +, -, *, / } のところをそれを使う形で書けば，「コードの見た目上には」そういう場所を減らすことはできる気はする．

//こういうのの中に件の if constexpr を入れれば「見た目には１か所」に．
//BinOP には std::plus<int> とかを指定する．
template< typename Ctxt_t, typename BinOP >
EvalFunc<Ctxt_t> CreateBinaryOpFunc( EvalFunc<Ctxt_t> LHS, EvalFunc<Ctxt_t> RHS )
{
	if constexpr( std::is_void_v<Ctxt_t> )
	{	return [lhs=std::move(LHS), rhs=std::move(RHS)](){	return BinOP()( lhs(), rhs() );	};	}
	else
	{	return [lhs=std::move(LHS), rhs=std::move(RHS)]( const Ctxt_t &Ctxt ){	return BinOP()( lhs(Ctxt), rhs(Ctxt) );	};	}
}

が，つーかこれ，そもそも 「 void の場合を特殊化して～」という実装の仕方自体がダメである気がする．
引数が｛有る場合，無い場合｝の両方で使えるようにするなら

//引数は 0 個以上
template< typename ...CTXTS >
using EvalFunc = std::function< int( const CTXTS &... ) >;

とすれば良いのではなかろうか．
そしたら if constexpr( std::is_void_v<Ctxt_t> ) なんてのは要らなくなるよね．

関数呼ぶ箇所に毎回 template 型引数を書くのがだるいので，static メンバ関数しかない class template 内に書いちゃう…のは有りなのか？ 
template< typename ...CTXTS >
class Parser
{
public:
	static EvalFunc<CTXTS...> Parse( const std::vector<std::string_view> &Tokens )
	{
		std::queue<std::string> TokenQ;
		for( const auto &token : Tokens ){	TokenQ.emplace( token );	}

		if( auto Result = Parse_Plus(TokenQ);	TokenQ.empty() )
		{	return Result;	}
		else
		{	throw std::invalid_argument( "Process stopped in the middle" );	}
	}

private:
	Parser() = delete;

	static EvalFunc<CTXTS...> Parse_Plus( std::queue<std::string> &Tokens )
	{
		if( Tokens.empty() ){	throw std::invalid_argument( "Missing Token" );	}
		auto Result = Parse_Value( Tokens );
		while( !Tokens.empty() )
		{
			if( Tokens.front() == "+" )
			{
				Tokens.pop();
				Result = [lhs=std::move(Result), rhs=Parse_Value( Tokens )]( const CTXTS &... Ctxts )
					{	return ( lhs(Ctxts...) + rhs(Ctxts...) );	};
			}
			else
			{	break;	}
		}
		return Result;
	}

	static EvalFunc<CTXTS...> Parse_Value( std::queue<std::string> &Tokens )
	{
		if( Tokens.empty() ){	throw std::invalid_argument( "Missing Token" );	}

		auto token = Tokens.front();
		Tokens.pop();
		if( auto value_ = StrToLong( token );	value_ )
		{	return [val=value_.value()]( const CTXTS &... ){	return val;	};	}
		else if( auto F = Parse_Symbol<CTXTS...>( token );	F )
		{	return F;	}
		else
		{	throw std::invalid_argument( "invalid token : " + token );	}
	}
};

段階を分ける？

それはそれとして，「段階を分けてみるべきでは」という旨のコメントをいただいたので，別途，その方向で考えてみた．

0
0
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?