求24点，算术式解析
题目：
给定任意4个正整数，利⽤用加，减，乘，除，括号这⼏几个运算符，编程计
算所有由这4个数字计算出24的表达式，并输出计算表达式。
输出结果要求：加法，乘法需要去重，(( a + b ) * c) / d = 24 和 (( b + a)
* c ) / d = 24 视为同⼀一表达式，只输出任意⼀一个即可。
要求：请尝试⽤用测试驱动开发程序完成（TDD）
⽰示例1：
输⼊入：3 3 6 6
输出：((6/3)+6)*3 = 24
⽰示例2：
输⼊入：3 2 3 4
输出：⽆无解
⽰示例3：
输⼊入：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左右）