题解 | #24点运算#

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

unordered_map<string, int> CardtoNum = {{"A", 1}, {"2", 2}, {"3", 3}, {"4", 4}, {"5", 5}, {"6", 6},
    {"7", 7}, {"8", 8}, {"9", 9}, {"10", 10}, {"J", 11}, {"Q", 12}, {"K", 13}
}; //输入的字符映射到数字
unordered_map<int, string> NumtoCard = {{1, "A"}, {2, "2"}, {3, "3"}, {4, "4"}, {5, "5"}, {6, "6"},
    {7, "7"}, {8, "8"}, {9, "9"}, {10, "10"}, {11, "J"}, {12, "Q"}, {13, "K"}
}; //返回的数字映射到字符
const vector<char> Op = {'+', '-', '*', '/'}; //输出时符号映射

int cal(int a, int b, int op) { //运算
    if (op == 0)
        return a + b;
    else if (op == 1)
        return a - b;
    else if (op == 2)
        return a * b;
    else
        return a / b;
}
 
bool dfs(const vector<int>& nums, int start, int sum, int op,
         vector<int>&
         ops) { //查找这个数字顺序下有无合适的符号可以让结果等于24
    int newSum = cal(sum, nums[start], op);
    if (start == 3 && newSum == 24) //末尾比较是否到了24
        return true;
    else if (start == 3)
        return false;
    for (int i = 0; i < 4; i++) { //遍历所有情况的符号
        ops.push_back(i); //尝试每个符号
        if (dfs(nums, start + 1, newSum, i, ops)) //递归计算
            return true;
        ops.pop_back(); //回溯
    }
    return false;
}

int main() {
    vector<string> s(4);
    cin >> s[0] >> s[1] >> s[2] >> s[3]; //输入4个字符串
    vector<int> nums(4);
    for (int i = 0; i < 4; i++) {
        if (s[i] == "joker" || s[i] == "JOKER") { //遇到大小王
            cout << "ERROR" << endl;
            return 0;
        }
        nums[i] = CardtoNum[s[i]]; //字符串转数字
    }
    sort(nums.begin(), nums.end()); //排成递增序
    do {
        vector<int> ops;
        for (int i = 0; i < 4; i++) { //遍历开头四种运算符
            ops.push_back(i);
            if (dfs(nums, 1, nums[0], i,
                    ops)) { //递归计算这个顺序的顺子有无运算符可以完成
                cout << NumtoCard[nums[0]] << Op[ops[0]]
                     << NumtoCard[nums[1]] << Op[ops[1]]
                     << NumtoCard[nums[2]] << Op[ops[2]]
                     << NumtoCard[nums[3]] << endl;
                return 0;
            }
            ops.pop_back(); //回溯
        }
    } while (next_permutation(nums.begin(), nums.end())); //枚举所有的顺序
    cout << "NONE" << endl;
    return 0;
}