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;
	}
}
}