Java-1 2 3 4 5 6 7 8 9=158中填入合适+,-,*,或者不填,使得等式成立,要求输出所以结果

意见反馈 意见反馈 主题:991 回复:2082

Java-1 2 3 4 5 6 7 8 9=158中填入合适+,-,*,或者不填,使得等式成立,要求输出所以结果

浮生未歇 发布于 2016-10-30 字数 1240 浏览 1194 回复 4

1 2 3 4 5 6 7 8 9=158中填入合适+,-,*,或者不填,使得等式成立
具体要求如下:
1.输出所有可能结果
2.考虑算法效率
注意事项:
该等式符合四则运算规则,先乘后加减
这题是我自己改编的,百度上应该没有

发布下所有结果,以便校对.

/**
*
1+2+3*4+56+78+9=158
1+2+34+5*6*7-89=158
1+2+34+56+7*8+9=158
1+2+34+56-7+8*9=158
1+2*3+4*5+6*7+89=158
1+2*34+5+67+8+9=158
1+23+4*5+6*7+8*9=158
1+23-4+5*6*7-8*9=158
1+23-4+56-7+89=158
1+234-5*6-7*8+9=158
1-2+3+4+56+7+89=158
1-2+34+56+78-9=158
1-2-34+5*6*7-8-9=158
1-23*4*5-6+7*89=158
1-234+56*7+8-9=158
1*2+3*4+5+67+8*9=158
1*2+34*5-6-7+8-9=158
1*2-3+4*5+67+8*9=158
1*2-3+4*56+7-8*9=158
1*2-3+4*56-7*8-9=158
1*2-3+45+6*7+8*9=158
1*2*3*4-5+67+8*9=158
1*2*34+5+6+7+8*9=158
1*23+45-6+7+89=158
1*23*4+56-7+8+9=158
1*23*4-5+6+7*8+9=158
1*23*4-5+6-7+8*9=158
1*23*4-5*6+7+89=158
1*234+5+6-78-9=158
1*234-5-6+7-8*9=158
1*234-5-6-7*8-9=158
12+3*4-5+67+8*9=158
12+34+5*6-7+89=158
12*3+4*5+6+7+89=158
12*3-4+5*6+7+89=158
12*3-4-5+6*7+89=158
123+4-56+78+9=158
123-4-5*6+78-9=158
123*4-5*67-8+9=158
*/

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(4

灵芸 2017-08-29 4 楼

这个问题直接穷举的效率可以接受,但毫无疑问是有更高效率的算法的,类似于动态规划
这个问题妙就秒在两点上:1. 不能加括号 2. 没有除法(所以运算结果都是整数)

这个问题有个很有趣的性质:对于任意连续的m个数字来说,怎样让这m个数字构成的结果最大?
答案很简单,什么符号都不填的时候最大。证明很简单,就不详细说了。这个称为性质X。

首先考虑只有乘号的情况,设从第k位开始的m个数字,通过加乘号或不写,能组成的表达式和值的集合,记为G(k,m)
比如G(1,1) = {"1"=>1}
G(1,2) = {"12"=>2, "12"=>12}
等等
则:
G(k,m) = Union{n(k,m), G(k,m-a) * n(k+m-a, a)}
a = 1,...,m-1
其中
n_(k+m-a, a)是从第k+m-a个开始连续a个数字组成的整数。
例如:
G(1,3) = Union{G(1,2) 3, G(1,1) 23}
= {"1
23" => 6, "123" => 36, "1*23" => 23}
用程序怎么实现相信大家都能想到。

如果单纯这么计算的话,G的量会很大,并不见得会快很多。这时候就需要用性质X剪枝了:
要求最终的结果为158(或者其他某个数R)

xxxxx +/- G(k,m) +/-/ xxxxxx... = R
G(k,m)中的结果当然都是正数。如果G前面的符号是+,那么整个表达式有:
R = xxxxx + G(k,m) +/-/
xxxxxx... > -n(1,k-1) + G(k,m) - n(k+m, 10-k-m)
因此必须有G(k,m) < R + n(1,k-1) + n(k+m, 10-k-m)
除此以外的G的值不可能形成有效的表达式,可以从G里面移除。这样可以剪去很多无效的结果。
G前是负号的情况同样有
R = xxxxx - G(k,m) +/-/* xxxxxx... < n(1,k-1) - G(k,m) + n(k+m, 10-k-m)
即G(k,m) < n(1,k-1) + n(k+m, 10-k-m) - R。
因此综合起来,只需要保留满足G(k,m) < |R| + n(1,k-1) + n(k+m, 10-k-m)的结果即可。

记前m个数字通过添加任意符号或不填,能组成的表达式和值的集合为F(m)

F(m) = Union{G(1,m), F(m-k) + G(m-k+1, k), F(m-k) - G(m-k+1, k)}
同样利用:
F(m) +- xxxxxxxxxxxxxxx = R
因而
-n(m+1, 10 - m) + F(m) < R < n(m+1, 10 - m) + F(m)
确定F(m)的范围在
-n(m+1, 10 - m) + R < F(m) < n(m+1, 10 - m) + R
之间
利用这个条件剪枝,可以确保中间不会出现太多的可行结果。
最后F(10)即为所求。
参考程序(这是C#的,不知道和Java差多少):

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace NumberExp
{
class Program
{
//保存乘法子表达式的表达式树:包括最后一个乘数,和指向前半部分乘法子表达式树的指针。
class MulExpPointer
{
public List<MulExpPointer> AppendFrom { get; set; } //可能有多个返回同样值的不同表达式
public string AppendExp { get; set; }
//穷举所有可能的表达式
public IEnumerable<string> GetAllExpressions()
{
if (AppendFrom == null) //没有前项表达式的时候,直接返回最后一个数
yield return AppendExp;
else
{
foreach (var item in AppendFrom)
{
foreach (var exp in item.GetAllExpressions())
{
yield return exp + AppendExp; //乘号已经包括在AppendExp里面了
}
}
}
}
//计算表达式的数目
public long GetExpressionCount()
{
if (AppendFrom == null)
return 1;
else
{
long count = 0;
foreach (var item in AppendFrom)
{
count += item.GetExpressionCount();
}
return count;
}
}
}

    //保存完整表达式的表达式树:包括指向最后一个乘法子表达式树的指针,和指向前半部分子表达式树的指针,还有中间的符号
    class ExpPointer
    {
        public List&lt;ExpPointer&gt; AppendFrom { get; set; }
        public List&lt;MulExpPointer&gt; AppendExp { get; set; }
        public string AppendOperator { get; set; }
        public IEnumerable&lt;string&gt; GetAllExpressions()
        {
            if (AppendFrom == null)
            {
                foreach (var item in AppendExp)
                {
                    foreach (var exp in item.GetAllExpressions())
                    {
                        yield return exp;
                    }
                }
            }
            else
            {
                List&lt;string&gt; mulexps = new List&lt;string&gt;();
                foreach (var item in AppendExp)
                {
                    mulexps.AddRange(item.GetAllExpressions());
                }
                foreach (var item in AppendFrom)
                {
                    foreach (var exp in item.GetAllExpressions())
                    {
                        foreach (var appendexp in mulexps)
                        {
                            yield return exp + AppendOperator + appendexp;
                        }
                    }
                }
            }
        }
        public long GetExpressionCount()
        {
            if (AppendFrom == null)
            {
                long count = 0;
                foreach (var item in AppendExp)
                {
                    count += item.GetExpressionCount();
                }
                return count;
            }
            else
            {
                long c1 = 0, c2 = 0;
                foreach (var item in AppendExp)
                {
                    c1 += item.GetExpressionCount();
                }
                foreach (var item in AppendFrom)
                {
                    c2 += item.GetExpressionCount();
                }
                return c1 * c2;
            }
        }
    }

    //找出所有表达式的主程序
    static void OutputAllResults(string digits, Int64 result)
    {
        int len = digits.Length;
        //G[i,j]: i开始长度为j+1的字符串,不填符号或填乘号,能得到的所有结果的列表。按照结果的数值分类并排序。
        var G = new SortedDictionary&lt;Int64, List&lt;MulExpPointer&gt;&gt;[len, len];
        //F[i]: 字符串开头开始长度为i+1的字符串,不填符号或填+-*,能得到的所有结果的列表。按照结果的数值分类并排序。
        var F = new SortedDictionary&lt;Int64, List&lt;ExpPointer&gt;&gt;[len];
        //N[i,j]: i开始,长度为j+1的字符串代表的数字
        var N = new Int64[len, len];
        //计算N:连续数字串对应的数
        for (int i = 0; i &lt; len; i++)
        {
            N[i, 0] = digits[i] - '0';
            for (int j = 1; j + i &lt; len; j++)
            {
                N[i, j] = N[i, j - 1] * 10 + (digits[i + j] - '0');
            }
        }
        //计算G
        for (int i = 0; i &lt; len; i++)
        {
            //初始化G[i,0]
            G[i, 0] = new SortedDictionary&lt;long, List&lt;MulExpPointer&gt;&gt;();
            //只有一个字符,只有一种情况:一个乘号都不填的情况
            G[i, 0].Add(N[i, 0], new List&lt;MulExpPointer&gt;(new MulExpPointer[] { new MulExpPointer { AppendFrom = null, AppendExp = digits.Substring(i, 1) } }));
            //按长度从小到大计算
            for (int j = 1; j + i &lt; len; j++)
            {
                //利用特性X剪枝:考虑前后的数字,只有在符合条件的范围内才需要保留
                long limit = Math.Abs(result);
                if (i &gt; 0)
                {
                    limit += N[0, i - 1];
                }
                if (i + j + 1 &lt; len)
                {
                    limit += N[i + j + 1, len - i - j - 2];
                }
                //初始化
                G[i, j] = new SortedDictionary&lt;long, List&lt;MulExpPointer&gt;&gt;();
                var currentDic = G[i, j];
                //一个乘号都不添加的情况
                currentDic.Add(N[i, j], new List&lt;MulExpPointer&gt;(new MulExpPointer[] { new MulExpPointer { AppendFrom = null, AppendExp = digits.Substring(i, j + 1) } }));
                //穷举最后一个数的长度
                for (int k = 0; k &lt; j; k++)
                {
                    //乘数已经在N里面算过了
                    long mul = N[i + j - k, k];
                    //可以通过G[i, j - k - 1] * N[i + j - k, k]来计算
                    foreach (var item in G[i, j - k - 1])
                    {
                        long v = item.Key * mul;
                        //由于item.Key从小到大排序,超过之后就可以不再计算
                        if (v &gt; limit)
                            break;
                        List&lt;MulExpPointer&gt; list;
                        if (currentDic.TryGetValue(v, out list))        //当前表里面已经有这个结果了。添加到Dictionary对应的List里面
                        {
                            list.Add(new MulExpPointer() { AppendFrom = item.Value, AppendExp = @"*" + digits.Substring(i + j - k, k + 1) });
                        }
                        else                                            //一个新的可以算出的数,添加到Dictionary里面
                        {
                            currentDic.Add(v, new List&lt;MulExpPointer&gt;(new MulExpPointer[] { new MulExpPointer { AppendFrom = item.Value, AppendExp = @"*" + digits.Substring(i + j - k, k + 1) } }));
                        }
                    }
                }
            }
        }
        //计算F

        for (int i = 0; i &lt; len; i++)
        {
            //初始化
            var currDic = F[i] = new SortedDictionary&lt;long, List&lt;ExpPointer&gt;&gt;();
            //剪枝条件:因为后面所有的数最大不超过一个符号不加的值,如果加上这个值仍然小于,或者减去这个值仍然大于需要的结果,就可以剪枝
            long floorVal = result;
            long ceilVal = result;
            if (i &lt; len - 1)
            {
                floorVal -= N[i + 1, len - i - 2];
                ceilVal += N[i + 1, len - i - 2];
            }
            //没有添加+或-的情况
            //不允许前置负号
            foreach (var g in G[0, i])
            {
                if (g.Key &gt; ceilVal)     //超出范围剪枝
                    break;
                if (floorVal &lt;= g.Key)       //剪枝
                {
                    currDic.Add(g.Key, new List&lt;ExpPointer&gt;(new ExpPointer[] { new ExpPointer() { AppendFrom = null, AppendExp = g.Value } }));   //加入Dictionary。由于g不重复,这里不需要判重。
                }
            }
            for (int j = 0; j &lt; i; j++)
            {
                foreach (var f in F[i - j - 1])
                {
                    if (f.Key - N[i - j, j] &gt; ceilVal)
                        break;
                    if (f.Key + N[i - j, j] &lt; floorVal)
                        continue;
                    if (f.Key &gt;= floorVal)           //剪枝条件:超过最小值之后才能减,否则越减越小了,不在范围内
                    {
                        //允许减
                        foreach (var g in G[i - j, j])
                        {
                            long v = f.Key - g.Key; //F[i - j - 1] - G[i - j ,j],在第i - j - 1个数后面加减号,可能得到的结果
                            if (v &lt; floorVal)
                                break;
                            if (v &lt;= ceilVal)
                            {
                                List&lt;ExpPointer&gt; list;
                                if (currDic.TryGetValue(v, out list))
                                {
                                    list.Add(new ExpPointer() { AppendFrom = f.Value, AppendOperator = "-", AppendExp = g.Value });
                                }
                                else
                                {
                                    currDic.Add(v, new List&lt;ExpPointer&gt;() { new ExpPointer() { AppendFrom = f.Value, AppendOperator = "-", AppendExp = g.Value } });
                                }
                            }
                        }
                    }
                    if (f.Key &lt;= ceilVal)        //同上
                    {
                        //允许加
                        foreach (var g in G[i - j, j])
                        {
                            long v = f.Key + g.Key;
                            if (v &gt; ceilVal)
                                break;
                            if (v &gt;= floorVal)
                            {
                                List&lt;ExpPointer&gt; list;
                                if (currDic.TryGetValue(v, out list))
                                {
                                    list.Add(new ExpPointer() { AppendFrom = f.Value, AppendOperator = "+", AppendExp = g.Value });
                                }
                                else
                                {
                                    currDic.Add(v, new List&lt;ExpPointer&gt;() { new ExpPointer() { AppendFrom = f.Value, AppendOperator = "+", AppendExp = g.Value } });
                                }
                            }
                        }
                    }
                }
            }
        }
        //需要求的结果都存在了F[len-1][result]里面。首先判断有没有合法的值,如果有,穷举所有结果。
        List&lt;ExpPointer&gt; exps;
        if (!F[len - 1].TryGetValue(result, out exps))
        {
            Console.WriteLine("没有找到符合条件的表达式");
        }
        else
        {
            long count = 0;
            foreach (var item in exps)
            {
                foreach (var exp in item.GetAllExpressions())
                {
                    Console.WriteLine(exp);
                }
                count += item.GetExpressionCount();
            }
            Console.WriteLine("共有{0}种不同的表达式", count);
        }
    }

    static void Main(string[] args)
    {
        string digits = Console.ReadLine();
        if (!Regex.IsMatch(digits, @"^[0-9]+$"))
        {
            Console.Error.WriteLine(@"无效的数字串。");
            return;
        }
        Int64 r = Int64.Parse(Console.ReadLine());
        OutputAllResults(digits, r);
    }
}

}

运行结果:

1234+56-7+8+9
1+234+5+67+8+9
123
4-567-8+9
1+2+3
4+56+78+9
123+4-56+78+9
1234-5+6+78+9
1+2+34+56+7
8+9
1+234-56-78+9
12+345-6-7+8-9
1-234+567+8-9
1-2-34+5
67-8-9
1-2+34+56+78-9
123-4-5
6+78-9
1234-5-6-78-9
12-3+456-78-9
1
234+5+6-78-9
123+45+6+7+89
123+45-6+7+89
1-2+3+4+56+7+89
12
3-4+56+7+89
1
234-56+7+89
1+23-4+56-7+89
12+34+56-7+89
12
3-4-5+67+89
1+2
3+45+67+89
1234+5+6+7+89
1
234-5+6-7+89
1+2+34+56-7+89
1
2+34+5+67+89
1234-5+67+89
12+34-5+67+89
12-3+45+67+89
1
2-3+45+67+89
1+23+45+67+89
1
234-5-6+7-89
1
2-3+456+7-89
1+23-4+567-89
1+2+34+5
67-89
1-23
45-6+789

顺便用同样的程序可以算出:
123456789123456789 = 316
共有3450789种不同的表达式(耗时5秒以内)

夜无邪 2017-08-01 3 楼

主类。

 package com.test;

public class Main {
static String exp = "123456789";
static String[] c = { "+", "-", "*", "" };
static IExpression expression = new IExpression(null);;
static int i = 0;
static String exp1;
static String exp2;
static String exp3;
static String exp4;
static String exp5;
static String exp6;
static String exp7;
static String exp8;

public static void main(String[] args) {
    for (int j1 = 0; j1 &lt; 4; j1++) {
        exp1 = exp.substring(0, 1) + c[j1] + exp.substring(1);
        for (int j2 = 0; j2 &lt; 4; j2++) {
            exp2 = exp1.substring(0, exp1.length() - 7) + c[j2]
                    + exp1.substring(exp1.length() - 7, exp1.length());
            for (int j3 = 0; j3 &lt; 4; j3++) {
                exp3 = exp2.substring(0, exp2.length() - 6) + c[j3]
                        + exp2.substring(exp2.length() - 6, exp2.length());
                for (int j4 = 0; j4 &lt; 4; j4++) {
                    exp4 = exp3.substring(0, exp3.length() - 5)
                            + c[j4]
                            + exp3.substring(exp3.length() - 5,
                                    exp3.length());
                    for (int j5 = 0; j5 &lt; 4; j5++) {
                        exp5 = exp4.substring(0, exp4.length() - 4)
                                + c[j5]
                                + exp4.substring(exp4.length() - 4,
                                        exp4.length());
                        for (int j6 = 0; j6 &lt; 4; j6++) {
                            exp6 = exp5.substring(0, exp5.length() - 3)
                                    + c[j6]
                                    + exp5.substring(exp5.length() - 3,
                                            exp5.length());
                            for (int j7 = 0; j7 &lt; 4; j7++) {
                                exp7 = exp6.substring(0, exp6.length() - 2)
                                        + c[j7]
                                        + exp6.substring(exp6.length() - 2,
                                                exp6.length());
                                for (int j8 = 0; j8 &lt; 4; j8++) {
                                    exp8 = exp7.substring(0,
                                            exp7.length() - 1)
                                            + c[j8]
                                            + exp7.substring(
                                                    exp7.length() - 1,
                                                    exp7.length());
                                    expression = new IExpression(null);
                                    int sum = getAnswer(exp8);
                                    // System.out.println("sum = " + sum);
//此处的158可随意更改为其他值                       if (sum == 158) {
                                        System.out.println("第" + (++i)
                                                + "个 exp = " + exp8);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    /*
     * 测试用
     */
    // System.out.println("1234567+8*9 == " + Anally("1234567+8*9"));
    // expression = new IExpression(null);
    // System.out.println("1234567+89 == " + Anally("1234567+89"));
    // expression = new IExpression(null);
    // System.out.println("123456*789 == " + Anally("123456*789"));
    System.exit(0);
}

/**
 * 解析表达式
 * 
 * @param exp
 */
public static int getAnswer(String exp2) {
    char[] chars = exp2.toCharArray();
    char lastChar = '0';
    int num = 0;
    for (char c1 : chars) {
        if (c1 &gt;= '0' &amp;&amp; c1 &lt;= '9') {
            if (lastChar + 1 == c1) {
                num = num * 10 + Integer.parseInt(c1 + "");
            }
            lastChar = c1;
        } else {
            expression.b = num;
            if (expression instanceof Mul) {
                expression.a.b = expression.a.b * num;
                expression = expression.a;
            }
            num = 0;
            switch (c1) {
            case '+':
                expression = new Add(expression);
                break;
            case '-':
                expression = new Sub(expression);
                break;
            case '*':
                expression = new Mul(expression);
                break;
            }
        }
    }
    expression.b = num;
    if (expression instanceof Mul) {
        expression = expression.a;
        expression.b = expression.b * num;
    }
    // 表达式解析完了,返回表达式的值
    return expression.doExpression();
}

}

附类

 package com.test;
/**

  • 加法表达式
  • @author Administrator
  • */
    public class Add extends IExpression{
    public Add(IExpression a) {
    super(a);
    // TODO Auto-generated constructor stub
    }
    @Override
    public int doExpression() {
    // TODO Auto-generated method stub
    return a.doExpression()+b;
    }

}

 package com.test;

/**

  • 表达式的基类,不弄成抽象类是为了方便作为链表的头
  • @author Administrator
  • */
    public class IExpression {
    public IExpression(IExpression a) {
    this.a = a;
    }
    IExpression a;
    int b;
    public int doExpression() {
    return b;
    };
    }

 package com.test;
/**

  • @author Administrator
  • /
    public class Mul extends IExpression{
    public Mul(IExpression a) {
    super(a);
    }
    @Override
    public int doExpression() {
    return a.doExpression()
    b;
    }

}

 package com.test;
/**

  • 减法
  • @author Administrator
  • */
    public class Sub extends IExpression{
    public Sub(IExpression a) {
    super(a);
    // TODO Auto-generated constructor stub
    }
    @Override
    public int doExpression() {
    return a.doExpression()-b;
    }

}

运行结果:

 第1个 exp = 1+2-3+456-7-8-9
第2个 exp = 1+2-3
4+567+8-9
第3个 exp = 1+2345-6+7-89
第4个 exp = 1+2
345-6-78-9
第5个 exp = 1+23+45+67+89
第6个 exp = 1+23+45+6
7+89
第7个 exp = 1+234+5+6+7+89
第8个 exp = 1+234+5
6+7-89
第9个 exp = 1+234+5
6-78-9
第10个 exp = 1+234-5+6
7-89
第11个 exp = 1+234-5-6-7-8-9
第12个 exp = 1-2+3
45+67+8-9
第13个 exp = 1-23+456+7-89
第14个 exp = 1-2
3+456-78-9
第15个 exp = 1-23-4+567+8-9
第16个 exp = 1
2+345-6+78-9
第17个 exp = 1
2-3+45+67+89
第18个 exp = 12-3+456-78+9
第19个 exp = 123+456-78+9
第20个 exp = 12+3+4
56+78+9
第21个 exp = 12+3+456-7+89
第22个 exp = 12+3
45+6+78-9
第23个 exp = 12+34
5-6+7+8+9
第24个 exp = 12-3+456-7-89
第25个 exp = 123+4+5+67-8+9
第26个 exp = 123-4+5-6-7+89

上面是我写的一个实现方式,效率就不知道了。基本思路是:自动根据题目生成一个表达式,然后再计算这个表达式的值,再判断是否跟想要的相等。

想挽留 2017-04-14 2 楼

遍历所有表达式判断结果

 import java.util.Stack;
public class StringTest {
int sum = 158;
int[] element = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int num = 1;
// 计算一个运算符号的计算结果
public void calculator(Stack<Integer> numStack, Stack<String> symbolStack) {
String symbol = symbolStack.pop();
int a = numStack.pop();
int b = numStack.pop();
b = "+".equals(symbol) ? numStack.push(a + b)
: "-".equals(symbol) ? numStack.push(b - a) : ""
.equals(symbol) ? numStack.push(a
b) : null;
}
/**

  • 计算表达式值,逻辑为判断运算符优先级 优先级分别为: (*) > (+) = (-) 计算规则为,下一个运算符>栈顶运算符,则下个运算符入栈
  • 下一个运算符<=栈顶运算符,则先取出栈顶运算符计算,计算结果重新入栈
  • @param expression
  • @return
    /
    public int checkValue(String expression) {
    // 数字栈
    Stack<Integer> numStack = new Stack<Integer>();
    // 运算符栈
    Stack<String> symbolStack = new Stack<String>();
    int numTmp = 0;
    String peek = "";
    for (int i = 0; i < expression.length(); i++) {
    char c = expression.charAt(i);
    if (c >= '0' && c <= '9') {
    numTmp = (numTmp == 0) ? c - 48 : numTmp
    10 + c - 48;
    } else {// 运算符
    // 上一个数字入栈
    numStack.push(numTmp);
    numTmp = 0;
    // 若栈顶不为空,判断运算符优先级
    if (!symbolStack.empty()) {
    peek = symbolStack.peek();
    if ("".equals(peek)) {
    calculator(numStack, symbolStack);
    }
    if (!(c == '
    ') && !symbolStack.empty()) {
    calculator(numStack, symbolStack);
    }
    }
    symbolStack.push(c + "");
    }
    }
    // 最后一个数字入栈
    numStack.push(numTmp);
    // 剩余的运算符计算
    while (!symbolStack.empty()) {
    calculator(numStack, symbolStack);
    }
    // 判断结果
    int result = numStack.pop();
    if (result == sum) {
    System.out.println(num++ + ":" + expression + "=" + sum);
    }
    return result;
    }
    // 递归所有表达式
    public void getExpression(String expression, int cursor) {
    if (cursor >= element.length) {
    checkValue(expression);
    return;
    }
    for (int i = 0; i < 4; i++) {
    getExpression(expression

    • ((i == 0) ? "+" + element[cursor] : (i == 1) ? "-"
      • element[cursor] : (i == 2) ? "*"
      • element[cursor] : element[cursor]), cursor + 1);
        }
        }
        public static void main(String[] args) {
        StringTest stringTest = new StringTest();
        stringTest.getExpression(stringTest.element[0] + "", 1);
        }
        }
归属感 2016-11-03 1 楼

可以从分割入手 然后填写符号
例如 先分割
1,2,3,4,5,6,7,8,9是一种
12,3,4,5,6,7,8,9第二种
123,4,5,6,7,8,9第三种
.
.
.
12345678,9//虽然不合法 但是也算一种
1,23,4,5,6,7,8,9
'
'
'
1,23456789//虽然不合法 但是也算一种
1,2,34,5,6,7,8,9
1,2,345,6,7,8,9
'
'
'
1,2,3456789
别忘记 还有一种组合
12,34,5,6,7,8,9
12,345,6,7,8,9
'
'
'
12,3456789
用此方法 分割出所有的字符串序列的组合
然后排除肯定不会..有的
例如1,2,3456789
序列最大数与(其他数字之和 )的差的绝对值 如果小于 158则排除(其实还有很多方法可以判断出来 例如定个上界 超过连续一半包括一半 就可以视为不符合要求 例如1234,56789或者1,234,56789)
然后合格的 用符号插入 ..验证是否为158