求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左右)