题解 | #24点游戏算法#

#include <climits>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;

int calculate(std::deque<int> &num, std::deque<char> &word)
{
    while (!word.empty())
    {
        char op = word.front();
        word.pop_front();
        int left = num.front();
        num.pop_front();
        if (op == '+' || op == '-')
        {
            if ((!word.empty() && (word.front() == '+' || word.front() == '-')) || word.empty())
            {
                int right = num.front();
                num.pop_front();
                if (op == '+')
                {
                    num.push_front(left + right);
                }
                else
                {
                    num.push_front(left - right);
                }
            }
            else
            {
                int right = calculate(num, word);
                if (op == '+')
                {
                    num.push_front(left + right);
                }
                else
                {
                    num.push_front(left - right);
                }
            }
        }
        else if (op == '*' || op == '/')
        {
            if (!word.empty() && word.front() != '(' || word.empty())
            {
                int right = num.front();
                num.pop_front();
                if (op == '*')
                {
                    num.push_front(left * right);
                }
                else
                {
                    if (!right)
                    {
                        num.push_front(INT_MAX);
                    }
				   ///这里题目是实数除法 是我理解有问题吗
                    else if (!(left % right))
                    {
                        num.push_front(left / right);
                    }
                    else
                    {
                        num.push_front(INT_MAX);
                    }
                }
            }
        }
        else if (op == '(')
        {
            std::deque<int> nums1;
            nums1.push_back(left);
            std::deque<char> word1;
            while (word.front() != ')')
            {
                word1.push_back(word.front());
                word.pop_front();
            }
            while (nums1.size() != word1.size() + 1)
            {
                nums1.push_back(num.front());
                num.pop_front();
            }
            // delete ')'
            word.pop_front();
            num.push_front(calculate(nums1, word1));
        }
        else
        {
            throw;
        }
    }
    return num.front();
}

bool isfind(std::deque<int> num, std::deque<char> word)
{
    int numcal = 0;
    if (word.size() >= 3)
    {
        int numcal = 0;
        int quote = 0;
        for (auto aa : word)
        {
            if (aa != '(' && aa != ')')
            {
                ++numcal;
            }
            else if (aa == '(')
            {
                quote++;
            }
            else if (aa == ')')
            {
                quote--;
            }
        }
        if (numcal > 3)
        {
            return false;
        }
        else if (numcal == 3 && !quote)
        {
            return calculate(num, word) == 24;
        }
    }

    int hoge = 0;
    auto a = word;
    a.push_back('+');
    if (isfind(num, a))
    {
        return true;
    }

    auto b = word;
    b.push_back('-');
    if (isfind(num, b))
    {
        return true;
    }

    auto c = word;
    c.push_back('*');
    if (isfind(num, c))
    {
        return true;
    }

    auto d = word;
    d.push_back('/');
    if (isfind(num, d))
    {
        return true;
    }

    int haveleft = false;
    int haveright = false;
    for (auto aa : word)
    {
        if (aa == '(')
        {
            haveleft = true;
        }
        else if (aa == ')')
        {
            haveright = true;
        }
    }
    if (!haveleft)
    {
        auto e = word;
        e.push_back('(');
        if (isfind(num, e))
        {
            return true;
        }
    }
    if (haveleft && !haveright && word.back() != '(')
    {
        auto f = word;
        f.push_back(')');
        if (isfind(num, f))
        {
            return true;
        }
    }
    return false;
}

bool dfs_visit(std::vector<int> &source, std::deque<int> &nums, vector<int> isget)
{
    if (nums.size() == 4)
    {
        auto nums1 = nums;
        return isfind(nums1, {});
    }
    for (size_t i = 0; i < source.size(); i++)
    {
        if (isget[i] == 0)
        {
            isget[i] = 1;
            nums.push_back(source[i]);
            if (dfs_visit(source, nums, isget))
            {
                return true;
            }
            nums.pop_back();
            isget[i] = 0;
        }
    }
    return false;
}

bool dfs(std::vector<int> &source)
{
    for (size_t i = 0; i < source.size(); i++)
    {
        vector<int> isget(4, 0);
        isget[i] = 1;
        std::deque<int> nums;
        nums.push_back(source[i]);
        if (dfs_visit(source, nums, isget))
        {
            return true;
        }
    }
    return false;
}

int main()
{
    int a, b, c, d;
    while (cin >> a >> b >> c >> d)
    {
        // 注意 while 处理多个 case
        std::vector<int> nums;
        nums.push_back(a);
        nums.push_back(b);
        nums.push_back(c);
        nums.push_back(d);
        if (dfs(nums))
        {
            cout << "true" << endl;
        }
        else
        {
            cout << "false" << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")

这个还写了好久，其实不是很难，记录一下