解法思想,全排列+递归。
#include <iostream>
#include <vector>
#include <stack>
#include <assert.h>
#include <algorithm>
using namespace std;
static inline int getValue(const std::string &str){
int ret=-1;
int len=str.size();
if(1==len){
if(isdigit(str.at(0))){
ret=str.at(0)-'0';
}else if('J'==str.at(0)){
ret=11;
}else if('Q'==str.at(0)){
ret=12;
}else if('K'==str.at(0)){
ret=13;
}else if('A'==str.at(0)){
ret=1;
}
}else if(2==len&&0==str.compare("10")){
ret=10;
}
return ret;
}
static inline int doCal(int a,int b,char op){
switch(op){
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
default:
return 0;
}
}
static inline char getOp(int i){
if(0==i){
return '+';
}else if(1==i){
return '-';
}else if(2==i){
return '*';
}else{
return '/';
}
}
char convertCard(int v){
if(v>=2&&v<=9){
return v+'0';
}else if(1==v){
return 'A';
}
if(11==v){
return 'J';
}else if(12==v){
return 'Q';
}else if(13==v){
return 'K';
}
//to make compiler happy.
return '0';
}
int check(const std::vector<int>& values,
std::vector<char>& ops){
int sum=0;
int a=values[0];
int b=values[1];
sum=doCal(a,b,ops[0]);
b=values[2];
sum=doCal(sum,b,ops[1]);
b=values[3];
sum=doCal(sum,b,ops[2]);
return sum;
}
class Solution{
public:
void recursion(const std::vector<int>& values,
std::vector<char>& ops){
if(3==ops.size()){
if(24==check(values,ops)){
int v=values.at(0);
if(10==v){
m_cache.push_back('1');
m_cache.push_back('0');
}else{
m_cache.push_back(convertCard(v));
}
for(int i=0;i<ops.size();i++){
m_cache.push_back(ops.at(i));
v=values.at(i+1);
if(10==v){
m_cache.push_back('1');
m_cache.push_back('0');
}else{
m_cache.push_back(convertCard(v));
}
}
m_flag=true;
}
return ;
}
for(int i=0;i<4;i++){
ops.push_back(getOp(i));
recursion(values,ops);
if(m_flag){
break;
}
ops.pop_back();
}
return ;
}
bool search(std::vector<int>& values,std::string &res){
m_flag=false;
m_cache.clear();
std::sort(values.begin(),values.end());
std::vector<char> ops;
do{
recursion(values,ops);
if(m_flag){break;}
}while(next_permutation(values.begin(),values.end()));
if(m_flag){
res=m_cache;
}
return m_flag;
}
private:
bool m_flag=false;
std::string m_cache;
};
int main(){
std::string inputs="A K 2 4";
std::string cards[4];
getline(std::cin,inputs);
std::vector<int> values;
int index=0;
std::string buffer;
for(int i=0;i<inputs.size();i++){
if(' '!=inputs.at(i)){
buffer.push_back(inputs.at(i));
}
if(inputs.size()-1==i&&buffer.size()>0){
cards[index]=buffer;
buffer.clear();
index++;
}
if(' '==inputs.at(i)){
if(buffer.size()>0){
cards[index]=buffer;
buffer.clear();
index++;
}
}
}
for(int i=0;i<4;i++){
int ret=getValue(cards[i]);
if(-1==ret){
std::cout<<"ERROR"<<std::endl;
return 0;
}
values.push_back(ret);
}
Solution so;
std::string res;
bool ret=so.search(values,res);
if(ret){
std::cout<<res<<std::endl;
}else{
std::cout<<"NONE";
}
return 0;
}
Reference
[1] next_permutation 的原理和使用