java实现24点算法

题目： 随机给4个数，对其进行加减乘除运算，最终值为24，最终打印数学表达式。

思路：穷举4个整数的所有可能表达式，然后对表达式求值。

表达式求值： exp=(exp|num) operator (exp|num)

细节：

因为4种运算 + - * / 都是二元运算，二元运算符接收两个参数，输出计算结果，并参与后续计算。

四个整数，每次选择两个数字，一共有C（4,2）中排列方式。 对每一个排列都进行一次四则运算。

输出的时候需要考虑 用 （）  来表示优先级。

import java.util.ArrayList;
import java.util.Scanner;

/** 
*  @author   LilyLee
 * @date     2017年4月27日
 * @time     上午10:48:53
 * @Version  1.0
 * @email    [e-mail]
 *
 */
public class Sum24 {

public static void main(String[] args) {
// TODO Auto-generated method stub
Experssion exp= new Experssion();
Thinker ti=new Thinker(exp);
ArrayList<Integer> card=new ArrayList<Integer>();
int sum=24;
Scanner sc=new Scanner(System.in);
int t;
for(int i=0;i<4;i++){
t=sc.nextInt();
card.add(t);
}
ti.count(card,card.size()-1,sum);

}

}


class Experssion{
private ArrayList<Integer>num=new ArrayList<Integer>();
private ArrayList<String> sign=new ArrayList<String>();

public void add(int n){
num.add(n);
}

public void add(String s){
sign.add(s);
}

private int getPriority(String s){
if(sign.equals("+")) return 1;
if(sign.equals("-")) return 1;
if(sign.equals("*")) return 2;
if(sign.equals("/")) return 2;
return -1;
}

private String toString(int la){
if(la==0){
return num.get(0)+sign.get(0)+num.get(1);
}
else{
String result=this.toString(la-1);
if(getPriority(sign.get(la))>=getPriority(sign.get(la-1)))
result="("+result+")";
result+=sign.get(la)+num.get(la+1);
return result;
}
}

public String toString(){
return toString(2);
}

public void clear(){
num.clear();
sign.clear();
}

}


class Thinker{
private Experssion exp;
public Thinker(Experssion expp){
exp=expp;
}

public boolean count(ArrayList<Integer>array,int num, int target){
if(num==1){
if(array.get(0)+array.get(1)==target){
exp.add(array.get(0));
exp.add(array.get(1));
exp.add("+");
return true;
}

if(array.get(0)-array.get(1)==target){
exp.add(array.get(0));
exp.add(array.get(1));
exp.add("-");
return true;
}

if(array.get(1)-array.get(0)==target){
exp.add(array.get(1));
exp.add(array.get(0));
exp.add("-");
return true;
}

if(array.get(0)*array.get(1)==target){
exp.add(array.get(1));
exp.add(array.get(0));
exp.add("*");
return true;
}

if(array.get(0)*target==array.get(1)){
exp.add(array.get(0));
exp.add(array.get(1));
exp.add("/");
return true;
}

if(array.get(1)*target==array.get(0)){
exp.add(array.get(1));
exp.add(array.get(0));
exp.add("/");
return true;
}

return false;

}
else{
for(int current=0;current<array.size();current++){
ArrayList<Integer>array1=new ArrayList<Integer>();
int currentNum=array.get(current);

for(int i=0;i<array.size();i++){
if(i!=current){
array1.add(array.get(i));
}
}

if(count(array1,num-1,target-currentNum)){
exp.add("+");
exp.add(currentNum);
if(num==3){
System.out.println(exp.toString());
exp.clear();
}
if(num!=3) return true;
}
if(count(array1,num-1,target+currentNum)){
exp.add("-");
exp.add(currentNum);
if(num==3){
System.out.println(exp.toString());
exp.clear();
}
if(num!=3) return true;
}


if(count(array1,num-1,target*currentNum)){
exp.add("/");
exp.add(currentNum);
if(num==3){
System.out.println(exp.toString());
exp.clear();
}
if(num!=3) return true;
}

if(target%currentNum==0){
if(count(array1,num-1,(int)(target/currentNum))){
exp.add("*");
exp.add(currentNum);
if(num==3){
System.out.println(exp.toString());
exp.clear();
}
if(num!=3) return true;
}



}
}
return false;
}
}
}