24点游戏问题

输出：True or False

代码实现：

分析所有组合（情况数）：
3. 添加括号分为以下三种情况：eg:a+b*c-d

//1.全排列：用递归的思想求出全排列 void swap(int &a, int &b)//交换连个元素 { int tem; tem = a; a = b; b = tem; } //计算所有操作数的全排列 void CalAllPermutation(int *a, int first, int length, vector<vector<string>>&permutation) { if (first == length - 1)//如果递归到深层时，到最后交换的元素即时最后一个元素时就打印出来 { vector<string> permu(length); char itoa_buffer[64]; for (int i = 0; i < length; i++) { sprintf(itoa_buffer, "%d", a[i]); permu[i] = string(itoa_buffer); } permutation.push_back(permu); } else { for (int i = first; i < length; i++) {//循环遍历使得当前位置后边的每一个元素都和当前深度的第一个元素交换一次 swap(a[first], a[i]);//使得与第一个元素交换 CalAllPermutation(a, first + 1, length, permutation);//深入递归，此时已确定前边的元素，处理后边子序列的全排列形式。 swap(a[first], a[i]);//恢复交换之前的状态 } } } //计算所有运算符的组合 void CalOpSymbolCombination(string&sym, int ope_bit, int n, vector<string>&symbol) { if (ope_bit == n) { symbol.push_back(sym); return; } for (int i = 0; i < 4; i++) { switch (i) { case 0: sym[ope_bit] = '+'; break; case 1: sym[ope_bit] = '-'; break; case 2: sym[ope_bit] = '*'; break; case 3: sym[ope_bit] = 'http://www.zhimengzhe.com/'; break; default: break; } CalOpSymbolCombination(sym, ope_bit + 1, n, symbol); } } 2.2. 计算法表达式（四则混合运算）的值 2.2.1将中缀表达式变为后缀表达式

我们把平时所用的标准四则运算表达式，即“9+(3-1)×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间。

/****************************************************************************** Copyright (C), 2001-2013, Huawei Tech. Co., Ltd. ****************************************************************************** File Name : Version : Author : Created : 2013/03/12 Last Modified : Description : Function List : History : 1.Date : 2013/03/12 Author : Modification: Created file ******************************************************************************/ #include"OJ.h" #include<string> #include<vector> #include<stack> #include <iostream> #include<algorithm> #include<sstream> using namespace std; void CalOpSymbolSet(char(*symbol_set)[3]); static int IndexOfSymbol(char sym); static char CompareSymbolPriority(char sym1, char sym2);//比较符号优先级 static void PopSymbolToPostfixExpression(stack<char> &symbol_stack, vector<string> &postfix_expression); static vector<string> InfixToPostfixExpression(const string &infix_expression); static string int_to_string(const int n);//int to string static double CalSubExpressionResult(double a, double b, char symbol); static double CalPostfixExpressionValue(const vector<string>& postfix_expression); //运算符的优先关系比对表 static char symbol_priority[4][4] = { /* 符号优先级表 /* '+' '-' '*' 'http://www.zhimengzhe.com/' */ /* '+' */{ '=', '=', '<', '<',}, /* '-' */{ '=', '=', '<', '<',}, /* '*' */{ '>', '>', '=', '=',}, /* 'http://www.zhimengzhe.com/' */{ '>', '>', '=', '=' } }; bool Game24Points(int a, int b, int c, int d) { int num_array[4] = { a,b,c,d }; char symbol_set[64][3];//运算符号组合 string infix_expression;//中缀表达式 vector<string> postfix_expression;//后缀表达式 double expression_result = 0.0; //1. 计算符号组合 int count = 0; CalOpSymbolSet(symbol_set); //2.计算输入数字的字典序排列 sort(num_array, num_array + 4); do { for (int i = 0; i < 64; i++) for (int j = 0; j < 7; j++) { switch (j) { case 0://无括号类型 infix_expression = int_to_string(num_array[0]) + symbol_set[i][0] + int_to_string(num_array[1]) + symbol_set[i][1] + int_to_string(num_array[2]) + symbol_set[i][2] + int_to_string(num_array[3]); break; case 1://(a+b)*c-d类型 infix_expression = "(" + int_to_string(num_array[0]) + symbol_set[i][0] + int_to_string(num_array[1]) + ")" + symbol_set[i][1] + int_to_string(num_array[2]) + symbol_set[i][2] + int_to_string(num_array[3]); break; case 2://a+(b*c)-d类型 infix_expression = int_to_string(num_array[0]) + symbol_set[i][0] + "(" + int_to_string(num_array[1]) + symbol_set[i][1] + int_to_string(num_array[2]) + ")" + symbol_set[i][2] + int_to_string(num_array[3]); break; case 3://a+b*(c-d)类型 infix_expression = int_to_string(num_array[0]) + symbol_set[i][0] + int_to_string(num_array[1]) + symbol_set[i][1] + "(" + int_to_string(num_array[2]) + symbol_set[i][2] + int_to_string(num_array[3]) + ")"; break; case 4://(a+b*c)-d类型 infix_expression = "(" + int_to_string(num_array[0]) + symbol_set[i][0] + int_to_string(num_array[1]) + symbol_set[i][1] + int_to_string(num_array[2]) + ")" + symbol_set[i][2] + int_to_string(num_array[3]); break; case 5://a+(b*c-d)类型 infix_expression = int_to_string(num_array[0]) + symbol_set[i][0] + "(" + int_to_string(num_array[1]) + symbol_set[i][1] + int_to_string(num_array[2]) + symbol_set[i][2] + int_to_string(num_array[3]) + ")"; break; case 6://(a+b)*(c-d)类型 infix_expression = "(" + int_to_string(num_array[0]) + symbol_set[i][0] + int_to_string(num_array[1]) + ")" + symbol_set[i][1] + "(" + int_to_string(num_array[2]) + symbol_set[i][2] + int_to_string(num_array[3]) + ")"; break; default: break; } postfix_expression = InfixToPostfixExpression(infix_expression); expression_result=CalPostfixExpressionValue(postfix_expression)-24; if (expression_result<0.001&&expression_result>(-0.001)) { cout<<infix_expression<<endl; return true; } } } while (next_permutation(num_array, num_array + 4));//求下一个字典序排列 return false; } string int_to_string(const int n) { ostringstream oss;//创建一个流 oss << n;//把值传递如流中 return oss.str();//返回转换后的字符串 } //1. 计算符号组合 void CalOpSymbolSet(char(*symbol_set)[3])//计算运算符组合(‘+’、‘-’、‘*’、‘/') { char sym[4] = { '+','-','*','http://www.zhimengzhe.com/' }; for (int i = 0; i < 4; i++) for (int j = 0; j < 4;j++) for (int k = 0; k < 4; k++) { (*symbol_set)[0] = sym[i]; (*symbol_set)[1] = sym[j]; (*symbol_set)[2] = sym[k]; ++symbol_set; } } //3. 中缀表达式变后缀表达式并计算值 vector<string> InfixToPostfixExpression(const string &infix_expression) { size_t i = 0; vector<string> postfix_expression; stack<char> symbol_stack;//符号栈 char ch = infix_expression[i++]; while (i <= infix_expression.size()) { if (isdigit(ch))//1.遇到数字，直接输出 { string digit; while (isdigit(ch)) { digit.push_back(ch); ch = infix_expression[i++]; } postfix_expression.push_back(digit); } else { if (symbol_stack.empty()||ch=='('||symbol_stack.top()=='(')//2.遇到符号：栈为空或符号为'('或栈顶为‘(',符号直接入栈 { symbol_stack.push(ch); ch = infix_expression[i++]; } else if (ch == ')')//3. 遇到右括号，弹出所有栈中符号直到左括号并输出（左括号不输出） { while (symbol_stack.top()!='(') { PopSymbolToPostfixExpression(symbol_stack, postfix_expression); } symbol_stack.pop();//弹出左括号，不输出 ch = infix_expression[i++]; } else { while (!symbol_stack.empty()) { char sym_priority = CompareSymbolPriority(symbol_stack.top(), ch); if (sym_priority == '>' || sym_priority == '=')//4.弹出优先级大于等于ch的所有符号 PopSymbolToPostfixExpression(symbol_stack, postfix_expression); else break; } symbol_stack.push(ch);//压入符号 ch = infix_expression[i++]; } } } while (!symbol_stack.empty())//弹出栈中剩余符号 { PopSymbolToPostfixExpression(symbol_stack, postfix_expression); } return postfix_expression; } //弹出栈中符号并输出到后缀表达式 void PopSymbolToPostfixExpression(stack<char> &symbol_stack, vector<string> &postfix_expression) { if (symbol_stack.empty()) return; string a(1, '#'); a[0] = symbol_stack.top(); symbol_stack.pop(); postfix_expression.push_back(a); } //3. 计算后缀表达式的值 double CalPostfixExpressionValue(const vector<string>& postfix_expression) { stack<double> exp_data; for (size_t i=0;i<postfix_expression.size();i++) { if(isdigit(postfix_expression[i][0])) { double data = atof(postfix_expression[i].c_str()); exp_data.push(data); } else { double num1,num2; num2 = exp_data.top(); exp_data.pop(); num1 = exp_data.top(); exp_data.pop(); double temp_result= CalSubExpressionResult(num1,num2,postfix_expression[i][0]); exp_data.push(temp_result); } } return exp_data.top(); } char CompareSymbolPriority(char sym1, char sym2)//中缀变后缀比较符号优先级 { int index1 = IndexOfSymbol(sym1); int index2 = IndexOfSymbol(sym2); return symbol_priority[index1][index2]; } int IndexOfSymbol(char sym)//符号优先级索引 { int index; switch (sym) { case '+': index = 0; break; case '-': index = 1; break; case '*': index = 2; break; case 'http://www.zhimengzhe.com/': index = 3; break; case '(': index = 4; break; case ')': index = 5; break; case '=': index = 6; break; default: break; } return index; } double CalSubExpressionResult(double a, double b, char symbol) { double result = 0.0; switch (symbol) { case '+': result = a + b; break; case '-': result = a - b; break; case '*': result = a*b; break; case 'http://www.zhimengzhe.com/': result = a / b; break; default: break; } return result; }