24点卡牌游戏（C++）

编程入门行业动态更新时间:2024-10-18 14:19:09

24点<a href=https://www.elefans.com/category/jswz/34/1696341.html style= 卡牌游戏（C++）"/>

24点卡牌游戏（C++）

一题目

24点游戏是经典的纸牌益智游戏。
mfc是一个很优秀的同学，他学习认真，经常刷题，偶尔也会打打游戏来放松omfc最喜欢卡牌类型游戏24点。
游戏的规则是∶你会被分配抽取N张扑克牌，分别从A-K，其中我们规定牌面为A的牌，其数值为1点﹔牌面为J、Q、K的牌，其数值分别为11、12、13点：数字牌的点数与其所表示的数字一致。现在你可以通过移动这N张牌的任意次序。并在两两之间插入四种运算符号+、一、*、/ (注∶除法在这里仅考虑整除的情况，例如3/2=1，4/2=2)。经过上述操作后，我们按照运算顺序计算表达式的结果，如果结果恰好凑成24点，则游戏取得胜利。
现在，你被要求和卡牌大师mfc进行一局游戏，因此你需要实现一个程序来帮助你解决如下问题:
当你读入N张牌和其对应的数值，你有多少种方法能够恰好凑出24点，并且要输出每种方法的具体情况。我们规定:两种方法不同，当且仅当对应的两个表达式字符串不同。
例如:给出的5张牌为1、2、 3①、 3②、5，其中有两个数值3的牌，为了加以区分，我们暂时用下标来进行区分，但在实际测试数据中不会有任何区分。此时，方案1＋2 + 3①* 3＋5和方案1＋2* 3②*3①＋5是完全相同的解，在结果中只需要输出一次。

输入：

4

10

输出：

6+10/2+13

6+13+10/2

10/2+6+13

10/2+13+6

13+6+10/2

13+10/2+6

6

二分析

将读取的数放入vector容器中，并从小到大进行排序。
借助next_permutation（）产生所有数的全排列，并对该全排列依次进行操作3，4操作。
在每两个数之间插入运算符（借助多层循环或递归并利用枚举列出运算符插入顺序的所有可能）。
将插入运算符后的完整中缀表达式转成逆波兰表达式进行计算，如果计算结果为24则记录该中缀表达式。

三源代码

预编译、全局变量和函数声明

#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<stack>
using namespace std;
int N;//存放卡牌数
vector<char>op = { '+','-','*','/' };
vector<char>operation;//存放当前运算符
//将当前顺序的操作数和运算符转成中缀表达式，若该表达式的计算结果为24则返回该表达式否则返回空串
string cal(vector<int>& nums, vector<char>operation);
vector<string> dfs(vector<int>& nums);//产生当前排列的所有顺序
bool isNumber(string token) {//判断是否为数字return !(token == "+" || token == "-" || token == "*" || token == "/");
}
int InfixExpressionEvaluation(vector<string>& exception);计算当前顺序的操作数和运算符的结果

3.1 主函数体

int main(){	cin >> N;vector<int> nums(N, 0);for (int i = 0; i < N; i++) {cin >> nums[i];}sort(nums.begin(), nums.end());vector<string> finres;do {vector<string> res = dfs(nums);if (!res.empty()){for (string str : res)finres.push_back(str);}} while (next_permutation(nums.begin(), nums.end()));for (auto str : finres) {cout << str << endl;}cout << finres.size() << endl;system("pause");return 0;
}

3.2 将每次顺序的转中缀表达式

string cal(vector<int>& nums, vector<char>operation){vector<string> res;res.push_back(to_string(nums[0]));for (int i = 0, j = 1; i < operation.size(); i++, j++){switch (operation[i]){case '+':res.push_back("+");res.push_back(to_string(nums[j]));break;case '-':res.push_back("-");res.push_back(to_string(nums[j]));break;case '*':res.push_back("*");res.push_back(to_string(nums[j]));break;case '/':res.push_back("/");res.push_back(to_string(nums[j]));break;}}string rres = "";//判断计算结果是否为24if (InfixExpressionEvaluation(res) == 24) //将中缀表达式转成string格式for (string s : res)rres += s;return rres;
}

3.3 产生每个排列的全部顺序

vector<string> dfs(vector<int>& nums){//N决定了需要插入运算符的个数，进而决定了循环的层数vector<string> resv;if (N == 4) {for (int i = 0; i < op.size(); i++) {//三个循环枚举所有的操作符顺序可能for (int j = 0; j < op.size(); j++) {for (int k = 0; k < op.size(); k++) {operation = { op[i],op[j],op[k] };//枚举所有可能的运算符顺序string res = cal(nums, operation);//计算结果if (res != "")resv.push_back(res);}}}}else if (N == 5) {for (int i = 0; i < op.size(); i++) {//三个循环枚举所有的操作符顺序可能for (int j = 0; j < op.size(); j++) {for (int k = 0; k < op.size(); k++) {for (int n = 0; n < op.size(); n++) {operation = { op[i],op[j],op[k], op[n] };//枚举所有可能的运算符顺序string res = cal(nums, operation);//计算结果if (res != "")resv.push_back(res);}}}}}else {for (int i = 0; i < op.size(); i++) {//三个循环枚举所有的操作符顺序可能for (int j = 0; j < op.size(); j++) {for (int k = 0; k < op.size(); k++) {for (int n = 0; n < op.size(); n++) {for (int m = 0; m < op.size(); m++) {operation = { op[i],op[j],op[k], op[n], op[m] };//枚举所有可能的运算符顺序string res = cal(nums, operation);//计算结果if (res != "")resv.push_back(res);}}}}}}	return resv;
}

3.4 逆波兰表达式求值

int InversePolishevaluation(vector<string>& exception) {//逆波兰表达式求值//这里的表达式只涉及四则运算，不涉及括号stack<int> stk;int n = exception.size();for (int i = 0; i < n; i++) {string& exp = exception[i];if (isNumber(exp)) {stk.push(atoi(exp.c_str()));}else {int num2 = stk.top();stk.pop();int num1 = stk.top();stk.pop();switch (exp[0]) {case '+': stk.push(num1 + num2); break;case '-': stk.push(num1 - num2); break;case '*': stk.push(num1 * num2); break;case '/': stk.push(num1 / num2); break;}}}return stk.top();
}

3.5 中缀表达式转逆波兰表达式

int InfixExpressionEvaluation(vector<string>& exception) {//将中缀表达式转成逆波兰表达式stack<string> stk;vector<string> vt;int n = exception.size();for (int i = 0; i < n; i++) {string& exp = exception[i];if (isNumber(exp))vt.push_back(exp);else {out:if (exp == "*" || exp == "/") {if (stk.empty() || stk.top() == "+" || stk.top() == "-")stk.push(exp);else {vt.push_back(stk.top());stk.pop();goto out;}}else {if (stk.empty())stk.push(exp);else {vt.push_back(stk.top());stk.pop();goto out;}}}}while (!stk.empty()) {vt.push_back(stk.top());stk.pop();}return InversePolishevaluation(vt);
}