C++ 四則演算を再帰下降構文解析する

parse_calculator.cpp

#include<string>
#include<iostream>

// arg1   : 評価する式
// arg2   : 式の参照位置
// return : std::pair<構文解析結果,次の参照位置> 
using RESULT = std::pair < int, size_t > ;
RESULT expr(const std::string&, size_t);
RESULT term(const std::string&, size_t);
RESULT factor(const std::string&, size_t);
RESULT number(const std::string&, size_t);

int main(int argc, char *argv[])
{
	/*
	- 参考URL
	- http://dai1741.github.io/maximum-algo-2012/docs/parsing/
	- http://www.prefield.com/algorithm/string/parser.html
	- BNF記法  : 四則演算
	- <expr>   ::= <term> [ ('+'|'-') <term> ]*
	- <term>   ::= <factor> [ ('*'|'/') <factor> ]*
	- <factor> ::= '(' <expr> ')' | <number>
	- <number> :== (0|1|2|3|4|5|6|7|8|9)+

	- * は0回以上の繰り返し
	- + は1回以上の繰り返し
	- | は選択
	*/

	if (argc < 2)
	{
		std::cerr << "At least , one argument shoud have expression , like \"1+2*3+4\"" << std::endl;
		return 0;
	}
	// 引数に渡した式をすべて計算する
	for (int arg = 1; arg < argc; arg++)
	{
		int idx = 0;
		std::string expression(argv[arg]);
		const auto v = expr(expression, idx);
		std::cout << expression << " = " << v.first << std::endl;
//		std::cout << v.second << std::endl;
	}

	return 0;
}

RESULT expr(const std::string& s, size_t i)
{
	auto left = term(s, i);
	while (true)
	{
		const auto op = s[left.second];
		if ('+' == op)
		{
			// + 1 は '+'の分
			const auto right = term(s, left.second + 1);
			left.first  = left.first + right.first;
			left.second = right.second;
		}
		else if ('-' == op)
		{
			// + 1 は '-'の分
			const auto right = term(s, left.second + 1);
			left.first = left.first - right.first;
			left.second = right.second;
		}
		else
		{
			break;
		}
	}
	return left;
}
RESULT term(const std::string& s, size_t i)
{
	auto left = factor(s, i);

	while (true)
	{
		const auto op = s[left.second];
		if ('*' == op)
		{
			// + 1 は '*' の分
			const auto right = factor(s, left.second + 1);
			left.first  = left.first * right.first;
			left.second = right.second;
		}
		else if ('/' == op)
		{
			// + 1 は  '/' の分
			const auto right = factor(s, left.second + 1 );
			left.first  = left.first / right.first;
			left.second = right.second;
		}
		else
		{
			break;
		}
	}
	return left;
}
RESULT factor(const std::string& s, size_t i)
{
	if ('(' == s[i])
	{
		i++; // '('の分
		const auto value = expr(s, i);
		if (s[value.second] != ')')
		{
			std::cerr << "')' factor = " << s << ":" << i << std::endl;
		}
		return RESULT( value.first , value.second + 1 );
	}
	else {
		return number( s , i );
	}
}
RESULT number(const std::string& s, size_t i)
{
	std::string num;

	while ('0' <= s[i] && s[i] <= '9')
	{
		num.push_back(s[i]);
		i++;
	}
	if (num.empty())
	{
		std::cerr << "number = " << s << ":" << i << std::endl;
		return RESULT(0, i);
	}
	else
	{
		return RESULT(std::stoi(num), i);
	}
}

result_win.txt

>Calculator_Parser.exe "(1+2+3)*(4+5+6)" "1+2*6/(10-7)" "1+2*3+4" "1+2*(3+4)"
(1+2+3)*(4+5+6) = 90
1+2*6/(10-7) = 5
1+2*3+4 = 11
1+2*(3+4) = 15