leetcode679. 24 点游戏

相较于原题，增加了输出表达式的版本。
只测试了几个例子，有错请指正。
加括号部分的判断是想最大化精简括号，也可以不判断全部无脑放括号。 。

关于精简括号，容易错的就是3/1/(1/2)
作为除数的表达式，实际上都需要加括号。

class Solution {
public:
    static constexpr double eps = 1e-6;
    //const string sign[4] = {"+", "-", "*", "/"};
    bool judgePoint24(vector<int>& cards) {
        vector<double>tmp;                  
        vector<int>sign_info{5, 5, 5, 5};   // 记录符号，非表达式设为大于符号运算的0 1 2 3
        vector<string>expr;                 // 记录运算过程
        for(const auto& x : cards) {
            tmp.emplace_back((double)x);
            expr.emplace_back(to_string(x));
        }
        return solve(tmp, expr, sign_info);
    }
    bool solve(vector<double>& cards, vector<string>& expr, vector<int>& sign) {
        int n = cards.size();
        if(n == 0) return false;    
        if(n == 1) { 
            double ans = (double)fabs(cards[0]-24.0);
            if(ans < eps) {
                cout << cards[0] << " = " << expr[0] << endl;
                return true;
            }
            return false;
        }
        int f = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i == j) continue;
                vector<double>t;
                vector<string>t_expr;
                vector<int>t_sign;
                for(int k = 0; k < n; ++k) {
                    if(k == i || k == j) continue;
                    t.emplace_back(cards[k]);
                    t_expr.emplace_back(expr[k]);
                    t_sign.emplace_back(sign[k]);
                }
                
                for(int k = 0; k < 4; ++k) {
                    string tt = "";
                    t_sign.emplace_back(k);
                    if(k == 0) {
                        if(j > i) continue; // 交换律
                        // 加法不需要加括号
                        t.emplace_back(cards[i] + cards[j]);
                        tt += (expr[i] + "+" + expr[j]);
                        
                    } else if(k == 1) {
                        t.emplace_back(cards[i] - cards[j]);
                        tt += (expr[i] + "-");

                        // 减法的 减数如果是+或-表达式需要加括号
                        if(sign[j] < 2) {
                            tt += "(";
                            tt += expr[j];
                            tt += ")";
                        } else tt += expr[j];
                    }
                    else if(k == 2){
                        if(j > i) continue;

                        t.emplace_back(cards[i] * cards[j]);
                        //tt += (expr[i] + "*" + expr[j]);
                        // 乘法只有加减表达式需要加括号
                        if(sign[i] < k) {
                            tt += "(" + expr[i] + ")";
                        } else tt += expr[i];
                        tt += '*';
                        if(sign[j] < k) {
                            tt += "(" + expr[j] + ")";
                        } else tt += expr[j];
                    } else if(k == 3){
                        if(cards[j] < eps) continue;
                        
                        t.emplace_back(cards[i] / cards[j]);
                        // 被除数只有加减表达式需要加括号
                        if(sign[i] < 2) {
                            tt += "(" + expr[i] + ")";
                        } else tt += expr[i];
                        tt += '/';

                        // 作为除数，如果是表达式则都要加括号（考虑3/(1/2)=6）
                        if(sign[j] <= k) {
                            tt += "(" + expr[j] + ")";
                        } else tt += expr[j];
                       // cout << tt << endl;
                   // cout << tt << ' ' << cards[i] << '/' << cards[j] << " = " << t.back() << endl;
                    }
                    t_expr.emplace_back(tt);
                    f |= solve(t, t_expr, t_sign);  
                    //if(solve(t, t_expr, t_sign)) return true;
                    t.pop_back();
                    t_expr.pop_back();
                    t_sign.pop_back();
                }
            }
        }
        return f;
    }
};