<p>You are given an integer array <code>cards</code> of length <code>4</code>. You have four cards, each containing a number in the range <code>[1, 9]</code>. You should arrange the numbers on these cards in a mathematical expression using the operators <code>[&#39;+&#39;, &#39;-&#39;, &#39;*&#39;, &#39;/&#39;]</code> and the parentheses <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code> to get the value 24.</p>

<p>You are restricted with the following rules:</p>

<ul>
	<li>The division operator <code>&#39;/&#39;</code> represents real division, not integer division.

	<ul>
		<li>For example, <code>4 / (1 - 2 / 3) = 4 / (1 / 3) = 12</code>.</li>
	</ul>
	</li>
	<li>Every operation done is between two numbers. In particular, we cannot use <code>&#39;-&#39;</code> as a unary operator.
	<ul>
		<li>For example, if <code>cards = [1, 1, 1, 1]</code>, the expression <code>&quot;-1 - 1 - 1 - 1&quot;</code> is <strong>not allowed</strong>.</li>
	</ul>
	</li>
	<li>You cannot concatenate numbers together
	<ul>
		<li>For example, if <code>cards = [1, 2, 1, 2]</code>, the expression <code>&quot;12 + 12&quot;</code> is not valid.</li>
	</ul>
	</li>
</ul>

<p>Return <code>true</code> if you can get such expression that evaluates to <code>24</code>, and <code>false</code> otherwise.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cards = [4,1,8,7]
<strong>Output:</strong> true
<strong>Explanation:</strong> (8-4) * (7-1) = 24
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cards = [1,2,1,2]
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>cards.length == 4</code></li>
	<li><code>1 &lt;= cards[i] &lt;= 9</code></li>
</ul>

static const auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}();

struct Frac {
    int nume, deno;

    Frac(int _nume, int _deno): nume(_nume), deno(_deno) {
        simp();
    }
    void simp() {
        int gcdVal = gcd(nume, deno);
        if (gcdVal == 0) {
            cout << "Div 0! nume=" << nume << ", deno=" << deno << endl;
            return;
        }
        nume /= gcdVal;
        deno /= gcdVal;
    }

    friend Frac operator + (const Frac &, const Frac &);
    friend Frac operator - (const Frac &, const Frac &);
    friend Frac operator * (const Frac &, const Frac &);
    friend Frac operator / (const Frac &, const Frac &);
};

Frac operator + (const Frac &a, const Frac &b) {
    return Frac(
        a.nume * b.deno + a.deno * b.nume, 
        a.deno * b.deno
    );
}

Frac operator - (const Frac &a, const Frac &b) {
    return Frac(
        a.nume * b.deno - a.deno * b.nume, 
        a.deno * b.deno
    );
}

Frac operator * (const Frac &a, const Frac &b) {
    return Frac(a.nume * b.nume, a.deno * b.deno);
}

Frac operator / (const Frac &a, const Frac &b) {
    return Frac(a.nume * b.deno, a.deno * b.nume);
}

constexpr int AddToken = 10;
constexpr int MinusToken = 11;
constexpr int MulToken = 12;
constexpr int DivToken = 13;
constexpr array<int, 4> ops = {
    AddToken, MinusToken, MulToken, DivToken
};

struct DFS {
    vector<int> tokens, &cards;
    bool vis[4];

    DFS(vector<int> &_cards): cards(_cards) {
        memset(vis, 0, sizeof(vis));
        cards.insert(cards.end(), ops.begin(), ops.end());
    }

    bool evalSimpleExpr(vector<Frac> &numStack, int token) {
        if (token < 10 || token > 13) {
            cout << "Undefined Token: " << token << endl;
            return false;
        }
        if (numStack.size() < 2) {
            // cout << "Invalid numStack: size=" << 
                // numStack.size() << endl;
            return false;
        }

        Frac a = numStack.back();
        numStack.pop_back();
        Frac b = numStack.back();
        numStack.pop_back();

        switch (token) {
        case AddToken:      numStack.push_back(a + b); break;
        case MinusToken:    numStack.push_back(a - b); break;
        case MulToken:      numStack.push_back(a * b); break;
        case DivToken:      numStack.push_back(a / b); break;
        }
        
        return true;
    }
    
    bool eval() {
        vector<Frac> numStack;

        // for (int i = 0; i < tokens.size(); i++) {
        //     if (tokens[i] >= 1 && tokens[i] <= 9)
        //         cout << tokens[i] << " ";
        //     else {
        //         if (tokens[i] == AddToken)
        //             cout << "+ ";
        //         else if (tokens[i] == MinusToken)
        //             cout << "- ";
        //         else if (tokens[i] == MulToken)
        //             cout << "* ";
        //         else if (tokens[i] == DivToken)
        //             cout << "/ ";
        //     }
        // }
        // cout << endl;

        for (auto token : tokens) {
            if (token >= 1 && token <= 9) {
                numStack.push_back(Frac(token, 1));
            } else {
                if (!evalSimpleExpr(numStack, token))
                    return false;
            }
        }

        if (numStack.size() != 1)
            return false;
        
        // return numStack.back().nume == 24 &&
            // numStack.back().deno == 1;

        if (numStack.back().nume == 24 &&
            numStack.back().deno == 1) {
            // for (int i = 0; i < tokens.size(); i++) {
            //     if (tokens[i] >= 1 && tokens[i] <= 9)
            //         cout << tokens[i] << " ";
            //     else {
            //         if (tokens[i] == AddToken)
            //             cout << "+ ";
            //         else if (tokens[i] == MinusToken)
            //             cout << "- ";
            //         else if (tokens[i] == MulToken)
            //             cout << "* ";
            //         else if (tokens[i] == DivToken)
            //             cout << "/ ";
            //     }
            // }
            // cout << endl;
            return true;
        }
        return false;
    }

    bool partialEval() {
        vector<Frac> numStack;

        // for (int i = 0; i < tokens.size(); i++) {
        //     if (tokens[i] >= 1 && tokens[i] <= 9)
        //         cout << tokens[i] << " ";
        //     else {
        //         if (tokens[i] == AddToken)
        //             cout << '+ ';
        //         else if (tokens[i] == MinusToken)
        //             cout << '- ';
        //         else if (tokens[i] == MulToken)
        //             cout << '* ';
        //         else if (tokens[i] == DivToken)
        //             cout << '/ ';
        //     }
        // }
        // cout << endl;

        for (auto token : tokens) {
            if (token >= 1 && token <= 9) {
                numStack.push_back(Frac(token, 1));
            } else {
                if (!evalSimpleExpr(numStack, token))
                    return false;
            }
        }

        return true;
    }

    bool dfs() {
        if (tokens.size() == 7) {
            return eval();
        }
        
        for (int i = 0; i < cards.size(); i++) {
            if (i < 4 && vis[i])
                continue;
            if (i < 4)
                vis[i] = true;

            tokens.push_back(cards[i]);
            if (partialEval() && dfs())
                return true;

            tokens.pop_back();
            if (i < 4)
                vis[i] = false;
        }

        return false;
    }
};

class Solution {
public:
    bool judgePoint24(vector<int>& cards) {
        DFS solver(cards);
        return solver.dfs();
    }
};
36996