C++实现简单24点游戏

C++实现简单24点游戏攻略

1. 游戏规则

简单24点是一款数学类撕牌游戏，每局游戏给出四个1-10之间的数字，玩家需要通过加减乘除等操作使这四个数字的结果为24。每个数字只能使用一次，游戏时间为2分钟，所有与24有接近的结果都可得分。更多详细规则请参考简单24点规则

2. 实现思路

本游戏的实现思路主要是对四个数进行排列组合构成计算表达式，然后通过计算表达式得到最终结果，在比较结果是否为24即可。由于要涉及到对计算表达式的求解，因此本游戏使用后缀表达式（逆波兰表达式）进行求解。

后缀表达式主要是将中缀表达式转化为后缀表达式，然后通过栈的方式进行计算，得到计算结果。其中后缀表达式的转化可以采用中缀表达式转化为后缀表达式的算法，具体实现可参考中缀表达式转后缀表达式

3. 代码实现

下面是本游戏的核心代码，包括表达式转化为逆波兰表达式，计算逆波兰表达式结果以及构造符号排列等。

//将表达式转化为逆波兰表达式
string expression2RPN(const string s){
    string op = "+-*/()";
    map<char, int> pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    stack<char> opr;
    string ss = "";
    for (int i = 0;i < s.size();i++){
        if (isdigit(s[i])) ss += s[i];
        else if (op.find(s[i]) != string::npos){
            while (!opr.empty() && opr.top() != '(' && pr[s[i]] <= pr[opr.top()]){
                ss += opr.top(); opr.pop();
            }
            if (s[i] == ')') opr.pop();
            else opr.push(s[i]);
        }else return "error";
    }
    while (!opr.empty()) ss += opr.top(), opr.pop();
    return ss;
}

//计算逆波兰表达式结果
int RPN2result(const string s){
    stack<int> st;
    for (int i = 0;i < s.size();i++){
        if (isdigit(s[i])) st.push(s[i] - '0');
        else{
            int a = st.top(); st.pop();
            int b = st.top(); st.pop();
            switch (s[i]){
                case '+': st.push(b + a); break;
                case '-': st.push(b - a); break;
                case '*': st.push(b * a); break;
                case '/': st.push(b / a); break;
                default: return -1;
            }
        }
    }
    return st.top();
}

//对数字数组进行排列组合
bool next_permutation(vector<int>& v){
    int n = v.size(), i = n - 2, j = n - 1;
    while (i >= 0){
        if (v[i] < v[i + 1]) break;
        i--;
    }
    if (i < 0) return false;
    while (j > i){
        if (v[j] > v[i]) break;
        j--;
    }
    swap(v[i], v[j]);
    reverse(v.begin() + i + 1, v.end());
    return true;
}

//构造符号排列
bool next_expression_permutation(vector<char>& v,int pos){
    if(v.size() == pos) return true;
    vector<char> op = {'+', '-', '*', '/'};
    for(int i=pos;i<v.size();++i){
        if(i != pos && v[i] == v[pos]) continue;
        swap(v[i],v[pos]);
        if(v[pos] >='0' && v[pos] <='9') next_expression_permutation(v, pos+1);
        else for(char j:op){
            v[pos] = j;
            if(next_expression_permutation(v, pos+1)) return true;
        }
        swap(v[i],v[pos]);
    }
    return false;
}

//检查是否为24点
bool check_24_point(vector<int>& v){
    vector<char> op(3, 'A');
    vector<int> a;
    do{
        a.clear();
        vector<char> b(op);
        a.push_back(v[0]);
        a.push_back(v[1]);
        a.push_back(v[2]);
        a.push_back(v[3]);
        do{
            vector<int> s;
            s.push_back(a[0]);
            for(int i=0;i<3;++i){
                s.push_back(b[i]);
                s.push_back(a[i+1]);
            }
            if(RPN2result(expression2RPN(vtoa(s))) == 24) return true;
        }while(next_permutation(a));
    }while(next_expression_permutation(op, 0));
    return false;
}

对于以上代码的解释请参考代码说明

4. 示例说明

假如当前给定的四个数字分别为1,2,3,4，我么可以通过如下代码执行：

vector<int> a={1,2,3,4};
bool r = check_24_point(a);
if(r) cout<<"可以得到24点"<<endl;
else cout<<"不能得到24点"<<endl;

该代码的输出结果为 “可以得到24点”。

再假如当前给定的数字为3,4,5,6，我们可以通过如下代码执行：

vector<int> b={3,4,5,6};
bool r = check_24_point(b);
if(r) cout<<"可以得到24点"<<endl;
else cout<<"不能得到24点"<<endl;

该代码的输出结果为 “不能得到24点”。

通过以上示例的代码，我们可以方便实现简单24点游戏。