求24点，算术式解析

题目：给定任意4个正整数，利用加、减、乘、除和括号这几个运算符，编程计算所有由这4个数字得出24的表达式，并输出对应的计算式。

输出要求：加法和乘法需要去重，((a+b)*c)/d = 24 与 ((b+a)*c)/d = 24 视为同一表达式，只输出任意一个即可。

要求：请尝试用测试驱动开发（TDD）完成本题。

示例

• 输入：3 3 6 6 → 输出：((6/3)+6)*3 = 24
• 输入：3 2 3 4 → 输出：无解
• 输入：5 5 6 6 → 输出：
  • ((5+5)-6)*6 = 24
  • (5*5)-(6/6) = 24
  • ((5-6)+5)*6 = 24
  • (5-(6-5))*6 = 24
  • (6-(6/5))*5 = 24

分析

既然采用 TDD 开发，先分析数据的输出格式。4个数字始终有2对括号——这里不依赖四则运算优先级，全部用括号显式表示运算顺序。4个数字需要运算三次，2对括号恰好能完整表达，因此可以先编写算术表达式求值函数。

class Opt
{
public:
	string type;
	int data = 0;
};


bool isOpt(string c)
{
	if (c == "+")return true;
	else if (c == "-")return true;
	else if (c == "*")return true;
	else if (c == "/")return true;
	else if (c == "(")return true;
	else if (c == ")")return true;
	else if (c == " ")return true;

	return false;
}




int cal(std::stack<Opt> & _s)
{
	if (_s.size() < 3)return 0;

	Opt op3 = _s.top(); _s.pop();
	Opt op2 = _s.top(); _s.pop();
	Opt op1 = _s.top(); _s.pop();
	if (!_s.empty())_s.pop();
	int res = 0;
	string c = op2.type;

	if (c == "+")
	{
		res = op1.data + op3.data;
	}
	else if (c == "-")
	{
		res = op1.data - op3.data;
	}
	else if (c == "*")
	{
		res = op1.data * op3.data;
	}
	else if (c == "/")
	{
		res = op1.data / op3.data;
	}

	return res;

}




int ParseExp(string exp)
{
	exp.append(" ");
	std::stack<Opt> _s;
	int isNum = 0;
	string nums;

	for (int i = 0; i < exp.size(); i++)
	{
		string opt;
		opt.push_back(exp[i]);
		//cout << opt << endl;
		if (isOpt(opt))
		{
			if (isNum != 0)
			{
				int num = 0;
				for (int k = 0, exp = 1; k < isNum; exp *= 10, k++)
				{
					Opt s = _s.top();

					num += exp* std::stoi(s.type);
					_s.pop();
				}
				Opt op;
				op.data = num;
				_s.push(op);
				isNum = 0;
			}

			if (opt == ")")
			{
				Opt op;
				op.data = cal(_s);
				_s.push(op);
			}
			else
			{
				Opt op;
				op.type = opt;
				_s.push(op);
			}


		}
		else
		{
			++isNum;
			Opt op;
			op.type = opt;
			_s.push(op);
		}

	}
	_s.pop();
	return  cal(_s);



}

int main()
{
	//int a = 3, b = 3, c = 6, d = 6;
	//string exp = "((5+5)-6)*6 ";

	cout << ParseExp("((6/3)+6)*3") << endl;;
	cout << ParseExp("((5+5)-6)*6") << endl;;
	cout << ParseExp("(5*5)-(6/6)") << endl;;
    cout << ParseExp("((55-55)+55)*1") << endl;;


	system("pause");

	return 0;
}

运行输出 24 24 24 55，计算结果正确。

接下来需要生成所有组合，采用暴力枚举并剪枝不可能的情况（运行时间约 1.7 s），代码不再赘述。