整数4つを10にするやつを解く

題名のまんまです。
1,3,3,7 から　(1 + 7 / 3) * 3 みたいなパターンを導き出して計算します。

解法

再帰をぶん回す。全探索です。
括弧さえつかなければ、適当に演算子を全探索してevalすればいいが、問題は括弧の場所がめんどくさい。
全探索する手法も考えられるが、括弧を付ける位置は計算順序を変化させるだけなので、計算する2つの項を探索、2つの数字の組を計算し式を圧縮して再帰すれば良い

免責

・可読性が最悪
・多分無駄な計算が多い(dpできるらしい)
・ぐらいは誤差が出ます。(分母と分子のペアを持つことで誤差消えるらしい)
・計算過程は出ますが、最初から括弧がついた形で出力はされません。

#include <vector>
#include <string>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <functional>
#include <stack>
#include <map>
using namespace std;
 
bool isOp(string c){return c == "+" or c == "*" or c == "&" or c == "/" or c == ")" or c == "("; }
bool isOp(char c){return c == '+' or c == '*' or c == '&' or c == '/';}
bool isNum(char c){return ('0' <= c and c <= '9') || c == '-';}
bool isNum(string s){return !(isOp(s));}
constexpr double eps = 1e-6;

double interpreter(string lhs, string op, string rhs){
    double lh = stod(lhs); double rh = stod(rhs);
    if(op == "+") return lh + rh;
    if(op == "&") return lh - rh;
    if(op == "*") return lh * rh;
    if(rh == 0){
        return -99999999;
    }
    return lh / rh;
}
map<string,int>memo;
string ans = "";
void rec2(string exp,string& original, vector<string>path, int len = 3){
 
    vector<string>parser;
 
    for(auto c : exp){
        if(parser.empty()){
            parser.push_back(string(1,c));
        } else if(isOp(c)){
            parser.push_back(string(1,c));
        } else if(isOp(parser.back()) && isNum(c)){
            parser.push_back(string(1,c));
        } else {
            parser.back() += string(1,c);
        }
    }
    path.push_back(exp);
 
    if(len == 0){
        if(abs(10 - stod(parser.front())) <= eps && memo[original] == 0){
            memo[original] = 1;
            std::cout << "find !!" << endl;
            auto f = [](string s){
                string t;
                for(auto& c : s)
                    t.push_back(c ==  '&' ? '-' : c);
                return t;
            };
            cout << f(original) << endl;
            for(auto p : path){
                cout <<  f(p) << endl;
            }
        }
        return;
    }
    if(len >= 1){
        double value = interpreter(parser[0],parser[1],parser[2]);
        auto cp = to_string(value);
        if(len >= 2 ){
            cp += accumulate(parser.begin() + 3, parser.end(),""s,[](auto lhs, auto rhs){
                return lhs + rhs;
            });
        }
        rec2(cp,original,path,len - 1);
    }
    if(len >= 2){
        double value = interpreter(parser[2],parser[3],parser[4]);
        auto cp = parser[0] + parser[1] + to_string(value);
        if(len >= 3){
            cp += accumulate(parser.begin() + 5, parser.end(),""s,[](auto lhs, auto rhs){
            return lhs + rhs;
        });
        }
        rec2(cp,original,path,len - 1);
    }
    if(len >= 3){
        double value = interpreter(parser[4],parser[5], parser[6]);
        auto cp = accumulate(parser.begin(), parser.begin() + 4,""s,[](auto lhs, auto rhs){
            return lhs + rhs;
        }) + to_string(value);
        rec2(cp,original,path,len - 1);
    }
}
void  rec(string& op, string exp, vector<double>& in,int depth = 0){
    if(depth + 1 == in.size()){
        vector<string>p;
        rec2(exp,exp,p);
        return;
    } else {
        for(int i = 0; i < op.size(); ++i){
            string cp = exp;
            cp += op[i] + to_string(in[depth + 1]);
            rec(op,cp,in,depth + 1);
        }
    }
}
 
int main() {
    string in;
    string op = "+&/*";
 
    cin >> in;
    auto num = [&](){
        vector<double>res;
        string t;
        for(auto c : in){
            if(c == ','){
                res.push_back(stoi(t));
                t.clear();
 
            } else {
                t.push_back(c);
            }
        }
        res.push_back(stoi(t));
        return res;
    }();
    sort(num.begin(),num.end());
    do{
        rec(op,to_string(num[0]),num);
    } while(next_permutation(num.begin(),num.end()));

    return 0;
}