数字与运算符的深搜排列

最近新出的活动 数字谜题 一点也不简单，怎么算的呢这是😭

于是我想让计算机来帮我计算，把可能性都算一遍，把数字和+-x/的排列出来，然后先计算*/，再计算+- 但是我忽略了一个事就是有的时候也需要先计算+-

像今天关于 1 2 3 4 5 和 + - x x 得到24的结果可以是4*5+(3-1)*2, 但是由于我没有使用到（）,我只能遍历得到 4*5+3-1*2 以至于一直得不到24 呜呜，所以接下来的代码只针对不用（）就可以得到结果的题目😜（括号想想就好麻烦呀）

什么是深搜（dfs）呢，也就是把所有能走的路都走一遍, 因此当数据量过多的时候，就会非常耗时....

首先创建全局的变量

// 全部数字
static String []num = { "77", "1", "6", "1", "3", "13", "11"};
// 全部符号
static String [] operator = {"-", "-", "/", "+"};
// 最终结果
static String ansNum = "66";
// 数字个数和符合个数（主要用于我们在深搜中判断它们是不是都用上了）
static int numCount = num.length, operatorCount = operator.length;
// 一个标记，保证每个数字/字符只用一次
static boolean [] bn, bo;

public static void main(String[] args) {
    bn = new boolean[numCount];
    bo = new boolean[operatorCount];
    for( int i = 0 ; i < numCount; i++ )
        bn[i] = false;
    for( int i = 0 ; i < operatorCount; i++ )
        bo[i] = false;
    // fun(排列的字符串, 当前使用的数字个数，当前使用的字符个数， 该位置能否使用运算符)
    // 第一个位置不能是运算符
    fun( "", 0, 0, false );
}

排列函数， 排列好后去计算该排列字符串，如果是我们要的结果，就打印输出

private static void fun( String s, int kn, int ko, boolean flag) {
    // 当数字和符合全部用完 且最后一个位置不是符号，则去计算
    if( kn == numCount && ko == operatorCount && flag == true) {
        String ans = calculate(s);
        // 判断是不是 66 ，
	if( ans.equals(ansNum)) {
            System.out.println(s);
	}
	return;
    }
    //	当前位置可以是数字
    for( int i = 0 ; i < numCount ; i++ ) {
        if(bn[i] == false) {
            // 回溯， 深搜必备
            bn[i] = true;
            fun( s+num[i], kn+1, ko, true );
            bn[i] = false;
	}
    }
    //当前位置可以是符号（和上面代码差不多）
    if( flag == true ) {
	for( int j = 0 ; j < operatorCount ; j++ ) {
            if(bo[j] == false) {
		bo[j] = true;
		fun( s+operator[j], kn, ko+1, false );
		bo[j] = false;
	    }
	}
    }
}

依次计算 x / + - , 假如是1-3x4-5 发现x(乘号)，找出它前面和后面的数（3、4），并计算出来，替换掉1-12-5

        private static String calculate(String str) {
		String s = str;
		for( int i = 0 ; i < s.length() ; i++ ) {
                // x 号的下标
			int cindex = s.indexOf("x");
			if( cindex != -1 ) {
                            // find(x 号的下标， 当前字符串（随时会改变），符号)
                            s = find( cindex, s , "x");
                            // System.out.println(s);
			}
		}
		for( int i = 0 ; i < s.length() ; i++ ) {
			int cindex = s.indexOf("/");
			if( cindex != -1 ) {
				s = find( cindex, s , "/");
			}
		}
		for( int i = 0 ; i < s.length() ; i++ ) {
			int cindex = s.indexOf("+");
			if( cindex != -1 ) {
				s = find( cindex, s , "+");
			}
		}
		for( int i = 0 ; i < s.length() ; i++ ) {
			int cindex = s.indexOf("-");
			if( cindex != -1 ) {
				s = find( cindex, s , "-");
			}
		}
           // 将运算完的字符串返回回去
		return s;
        }

find 函数 ，找出符合前面和后面的数，并进行替换

private static String find(int cindex, String s, String op) {
		String a = "", b = "";
		for( int j = cindex-1; j >= 0; j-- ) {
			int ch = s.charAt(j)-'0';
			if( ch >= 0 && ch <= 9 ) {
				a = s.charAt(j) + a;
			}else {
				break;
			}
		}
		for( int j = cindex+1; j < s.length(); j++ ) {
			int ch = s.charAt(j)-'0';
			if( ch >= 0 && ch <= 9 ) {
				b = b + s.charAt(j);
			}else {
				break;
			}
		}
                // 将 "3x4" 替换为 "12"
		if( op == "x" ) {
			s = s.replace(a+"x"+b, Integer.toString(Integer.parseInt(a)*Integer.parseInt(b)));
		}
		if( op == "/" ) {
                // 除得尽我们才替换
			if( Integer.parseInt(a)%Integer.parseInt(b) == 0 )
				s = s.replace(a+"/"+b, Integer.toString(Integer.parseInt(a)/Integer.parseInt(b)));
		}
		if( op == "+" ) {
			s = s.replace(a+"+"+b, Integer.toString(Integer.parseInt(a)+Integer.parseInt(b)));
		}
           // 当字符串为 `-3+5+6` 负号前面没有数
		if( op == "-"  &&  a!="" ) {
			s = s.replace(a+"-"+b, Integer.toString(Integer.parseInt(a)-Integer.parseInt(b)));
		}
           // 可能会计算出来负数
		s = s.replace("+-", "-");
           s = s.replace("--", "+");
		return s;
	}

输出： 有重复应该是因为有重复数字组合的问题

这关过啦，虽然不能解决所有的关卡🧐🧐🧐