题解 | #24点运算#

首先吐槽一下这个OJ，这个答案明明是对的，害我看了好久！！

以下是AC代码（有详细的注释）：

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <stack>
using namespace std;
unordered_set<string> err {"joker", "JOKER"};
// 这个pri存储运算符对应的优先级，但其实并不需要，因为这道题是直接从左到右算的，我一开始以为要用中缀表达式就随手定义了
unordered_map<char, int> pri{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
int change(char s)    // 定义一个函数用来转换字符
{
    if (isdigit(s)) return s - '0';
    else if (s == 'A') return 1;
    else if (s == 'J') return 11;
    else if (s == 'Q') return 12;
    else if (s == 'K') return 13;
}
int cal(string path)    // 定义一个函数用来计算我们的终止状态表达式的值， path存储的是表达式
{
    stack<int> st;
    stack<char> stc;
    for (int i = 0; i < path.size(); ++i)
    {
        if (!pri.count(path[i]))    // 遇到数字
        {
            if (!stc.empty())    // 若本数字之前出现过运算符，直接计算
            {
                int a = st.top(); st.pop();
                int c = stc.top(); stc.pop();
                if (c == '+') a += change(path[i]);
                else if (c == '-') a -= change(path[i]);
                else if (c == '*') a *= change(path[i]);
                else a /= change(path[i]);
                st.push(a);    // 中间结果入栈
            }
            else st.push(change(path[i]));    // 之前无运算符，数字入栈
        }
        else stc.push(path[i]);    // 运算符直接入栈
    }
    return st.top();    // 最后栈里唯一的数就是表达式的值
}
int main()
{
    string a, b, c, d;
    cin >> a >> b >> c >> d;
    if (err.count(a) || err.count(b) || err.count(c) || err.count(d)) puts("ERROR");
    else
    {
        unordered_map<string, int> st;    //存储每个字符的次数，搜索时用来判断有没有字符可用
        st[a]++; st[b]++; st[c]++; st[d]++;
        char div[4] = {'+', '-', '*', '/'};
        string path = "";
        bool flag = false;    // 只需要一个答案，遇到正确答案用flag标识，直接退出搜索
        function<void(int)> dfs = [&](int x)
        {
            if (x == 4)
            {
                if (cal(path) == 24) 
                {
                    cout << path << endl;
                    flag = true;
                }
                return;
            }
            for (auto &p : st)    //遍历每一个字符
            {
                if (p.second)    // 若字符可用，则加到表达式path中
                {
                    p.second--;
                    path += p.first;
                    if (x != 3)    // x==3时为第四个数字，不需要添加运算符
                        for (int i = 0; i < 4; ++i)    //遍历所有运算符
                        {
                            path += div[i];
                            dfs(x + 1);
                            if (flag) return;
                            path.pop_back();
                        }
                    else dfs(x + 1);
                    if (flag) return;
                    path.pop_back();
                    p.second++;
                }
                if (flag) return;    // 退出可以用dfs返回bool值来做，代码会短一些，懒得改了
            }
        };
        dfs(0);
        if (!flag) puts("NONE");
    }
    return 0;
}