24点游戏的算法，貌似用二叉树。懂的人进来说说。谢谢！

Question

24点游戏的算法，貌似用二叉树。懂的人进来说说。谢谢！四个数，三个符号。运算出来的结果为24.

Answer 1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Reflection;
using System.Text.RegularExpressions;namespace MyCsStudy
{
    /// <summary>
    /// 24点算法
    /// </summary>
    class TwentyFour
    {
        public static List<string> listOps = new List<string>(); //存加减乘除运算符
        static TwentyFour()
        {
            listOps.Add("+");
            listOps.Add("-");
            listOps.Add("*");
            listOps.Add("/");
        }
        public static bool Computing(string[] numArr, int numLen, int targetNum)
        {
            bool flag = false;
            for (int i = 0; i < numLen; i++)
            {
                for (int j = i + 1; j < numLen; j++)
                {
                    string[] strij = new string[] { numArr[i], numArr[j] };
                    numArr[j] = numArr[numLen - 1];
                    for (int k = 0; k < listOps.Count; k++)
                    {
                        numArr[i] = "(" + strij[0] + listOps[k] + strij[1] + ")";
                        if (Computing(numArr, numLen - 1, targetNum))
                        {
                            flag = true;
                            return flag;
                        }
                    }
                    numArr[i] = strij[0];
                    numArr[j] = strij[1];
                }
            }
            System.Data.DataTable dt = new System.Data.DataTable();
            string expression = numArr[0];
            /*
             * 利用datatable的compute方法计算字符串表达式(不知c有没有类似方法)
             * 如果不用datatable的compute方法，不知还有没有其他c#函数？
             * 期待高手给出更直观的解答
             */
            object objNum = dt.Compute(expression, "");
            int result;
            int.TryParse(objNum.ToString(), out result);            //如果运算结果是预期的数字，而且数组中的数字全部在运算范畴内
            if (result == targetNum && numLen == 1)
                flag = true;
            return flag;
        }

Answer 2

我也可以参考这个：
http://blog.csdn.net/hj3793/article/details/1844148

Answer 3

to maco_wang
谢谢 不知道有没有二叉树的算法 我印象里好像有 

Answer 4

24点全解using System;
using System.Collections.Generic;
using System.Text;class TwentyFourProblem
{
    static void Main()
    {
        string datas = "";
        string operators = @"+_-_*_/_|_\";
        string temData = "";
        for (int i = 0; i < 4; i++)
            datas += Console.ReadLine() + "_";
        List<string> dataPermutations = new List<string>();
        List<string> operatorsCombinations = new List<string>();
        List<string> solutions = new List<string>();
        AllPermutation(datas, temData, dataPermutations);
        AllCombination(1, 3, operators, "", operatorsCombinations);
        foreach (string temDatas in dataPermutations)
            foreach (string temOperators in operatorsCombinations)
            {
                calculate(temDatas, temOperators, "", "", solutions);
            }
        foreach (string solution in solutions)
            Console.Write(solution + "\n");
        Console.Write("over");
    }
    private static void AllPermutation(string datas, string temData, List<string> permutations)
    {
        string[] data = datas.Split('_');
        for (int i = 0; i < data.Length - 1; i++)
        {
            if (data.Length == 2)
            {
                string temPermutation = temData + data[i];
                permutations.Add(temPermutation);
            }
            else
            {
                string tem = temData;
                temData += data[i] + '_';
                datas = "";
                for (int j = 0; j < data.Length - 1; j++)
                    if (j != i)
                        datas += data[j] + '_';
                AllPermutation(datas, temData, permutations);
                temData = tem;
            }
        }
    }    private static void AllCombination(int rankCount, int rank, string datas, string temCombination, List<string> combinations)
    {
        string[] data = datas.Split('_');
        for (int i = 0; i < data.Length; i++)
        {
            if (rankCount == rank)
                combinations.Add(temCombination + data[i]);
            else
            {
                string temStr = temCombination;
                temCombination += data[i] + "_";
                AllCombination(++rankCount, rank, datas, temCombination, combinations);
                rankCount--;
                temCombination = temStr;
            }
        }
    }    private static void calculate(string datas, string operators, string lastOperator, string temSolution, List<string> solutions)
    {
        string[] data = datas.Split('_');
        string[] temOperator = operators.Split('_');
        if (data.Length > 1)
        {
            string result = operatorOperation(data[0], data[1], temOperator[0]).ToString();
            if ((temOperator[0] == "\\" && lastOperator != "") || (temOperator[0] == "|" && (lastOperator == "-" || lastOperator == "+" || lastOperator == "|")) || ((temOperator[0] == "*" || temOperator[0] == "/") && (lastOperator == "+" || lastOperator == "-" || lastOperator == "|")))
            {
                temSolution = temSolution.Insert(0, "(");
                temSolution += ")";
            }
            if (data.Length == 4)
                temSolution += data[0];
            if (temOperator[0] == "|" || temOperator[0] == "\\")
            {
                string temOp = "";
                if (temOperator[0] == "|")
                    temOp = "-";
                else temOp = "/";
                temSolution = temSolution.Insert(0, data[1] + temOp);
            }
            else temSolution += temOperator[0] + data[1];
            string newDatas = "";
            string newOperators = "";
            for (int j = 2; j < data.Length; j++)
                newDatas += data[j] + "_";
            newDatas = newDatas.Insert(0, result + "_");
            for (int j = 1; j < temOperator.Length; j++)
                newOperators += temOperator[j] + "_";
            if (newOperators == "")
                newOperators = "?";
            calculate(newDatas.Substring(0, newDatas.Length - 1), newOperators.Substring(0, newOperators.Length - 1), temOperator[0], temSolution, solutions);
        }
        else if (data.Length == 1)
        {
            if (Math.Abs(double.Parse(data[0]) - 24) <= 0.000001)
                solutions.Add(temSolution);
        }
    }    private static double operatorOperation(string data1, string data2, string Operator)
    {
        double result = 0;
        double num1 = double.Parse(data1);
        double num2 = double.Parse(data2);
        switch (Operator)
        {
            case "+": result = num1 + num2; break;
            case "-": result = num1 - num2; break;
            case "*": result = num1 * num2; break;
            case "/": result = num1 / num2; break;
            case "|": result = num2 - num1; break;
            case "\\": result = num2 / num1; break;
        }
        return result;
    }
}