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

Question

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
     */

Answer 1

这个问题直接穷举的效率可以接受，但毫无疑问是有更高效率的算法的，类似于动态规划
这个问题妙就秒在两点上：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}
= {"123" => 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<ExpPointer> AppendFrom { get; set; }
public List<MulExpPointer> AppendExp { get; set; }
public string AppendOperator { get; set; }
public IEnumerable<string> GetAllExpressions()
{
if (AppendFrom == null)
{
foreach (var item in AppendExp)
{
foreach (var exp in item.GetAllExpressions())
{
yield return exp;
}
}
}
else
{
List<string> mulexps = new List<string>();
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<Int64, List<MulExpPointer>>[len, len];
//F[i]: 字符串开头开始长度为i+1的字符串，不填符号或填+-*，能得到的所有结果的列表。按照结果的数值分类并排序。
var F = new SortedDictionary<Int64, List<ExpPointer>>[len];
//N[i,j]: i开始，长度为j+1的字符串代表的数字
var N = new Int64[len, len];
//计算N：连续数字串对应的数
for (int i = 0; i < len; i++)
{
N[i, 0] = digits[i] - '0';
for (int j = 1; j + i < len; j++)
{
N[i, j] = N[i, j - 1] * 10 + (digits[i + j] - '0');
}
}
//计算G
for (int i = 0; i < len; i++)
{
//初始化G[i,0]
G[i, 0] = new SortedDictionary<long, List<MulExpPointer>>();
//只有一个字符，只有一种情况：一个乘号都不填的情况
G[i, 0].Add(N[i, 0], new List<MulExpPointer>(new MulExpPointer[] { new MulExpPointer { AppendFrom = null, AppendExp = digits.Substring(i, 1) } }));
//按长度从小到大计算
for (int j = 1; j + i < len; j++)
{
//利用特性X剪枝：考虑前后的数字，只有在符合条件的范围内才需要保留
long limit = Math.Abs(result);
if (i > 0)
{
limit += N[0, i - 1];
}
if (i + j + 1 < len)
{
limit += N[i + j + 1, len - i - j - 2];
}
//初始化
G[i, j] = new SortedDictionary<long, List<MulExpPointer>>();
var currentDic = G[i, j];
//一个乘号都不添加的情况
currentDic.Add(N[i, j], new List<MulExpPointer>(new MulExpPointer[] { new MulExpPointer { AppendFrom = null, AppendExp = digits.Substring(i, j + 1) } }));
//穷举最后一个数的长度
for (int k = 0; k < 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 > limit)
break;
List<MulExpPointer> 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<MulExpPointer>(new MulExpPointer[] { new MulExpPointer { AppendFrom = item.Value, AppendExp = @"*" + digits.Substring(i + j - k, k + 1) } }));
}
}
}
}
}
//计算F

for (int i = 0; i < len; i++)
{
//初始化
var currDic = F[i] = new SortedDictionary<long, List<ExpPointer>>();
//剪枝条件：因为后面所有的数最大不超过一个符号不加的值，如果加上这个值仍然小于，或者减去这个值仍然大于需要的结果，就可以剪枝
long floorVal = result;
long ceilVal = result;
if (i < 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 > ceilVal) //超出范围剪枝
break;
if (floorVal <= g.Key) //剪枝
{
currDic.Add(g.Key, new List<ExpPointer>(new ExpPointer[] { new ExpPointer() { AppendFrom = null, AppendExp = g.Value } })); //加入Dictionary。由于g不重复，这里不需要判重。
}
}
for (int j = 0; j < i; j++)
{
foreach (var f in F[i - j - 1])
{
if (f.Key - N[i - j, j] > ceilVal)
break;
if (f.Key + N[i - j, j] < floorVal)
continue;
if (f.Key >= 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 < floorVal)
break;
if (v <= ceilVal)
{
List<ExpPointer> list;
if (currDic.TryGetValue(v, out list))
{
list.Add(new ExpPointer() { AppendFrom = f.Value, AppendOperator = "-", AppendExp = g.Value });
}
else
{
currDic.Add(v, new List<ExpPointer>() { new ExpPointer() { AppendFrom = f.Value, AppendOperator = "-", AppendExp = g.Value } });
}
}
}
}
if (f.Key <= ceilVal) //同上
{
//允许加
foreach (var g in G[i - j, j])
{
long v = f.Key + g.Key;
if (v > ceilVal)
break;
if (v >= floorVal)
{
List<ExpPointer> list;
if (currDic.TryGetValue(v, out list))
{
list.Add(new ExpPointer() { AppendFrom = f.Value, AppendOperator = "+", AppendExp = g.Value });
}
else
{
currDic.Add(v, new List<ExpPointer>() { new ExpPointer() { AppendFrom = f.Value, AppendOperator = "+", AppendExp = g.Value } });
}
}
}
}
}
}
}
//需要求的结果都存在了F[len-1][result]里面。首先判断有没有合法的值，如果有，穷举所有结果。
List<ExpPointer> 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);
}
}
}

运行结果：

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

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

Answer 2

主类。

 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 < 4; j1++) {
exp1 = exp.substring(0, 1) + c[j1] + exp.substring(1);
for (int j2 = 0; j2 < 4; j2++) {
exp2 = exp1.substring(0, exp1.length() - 7) + c[j2]
+ exp1.substring(exp1.length() - 7, exp1.length());
for (int j3 = 0; j3 < 4; j3++) {
exp3 = exp2.substring(0, exp2.length() - 6) + c[j3]
+ exp2.substring(exp2.length() - 6, exp2.length());
for (int j4 = 0; j4 < 4; j4++) {
exp4 = exp3.substring(0, exp3.length() - 5)
+ c[j4]
+ exp3.substring(exp3.length() - 5,
exp3.length());
for (int j5 = 0; j5 < 4; j5++) {
exp5 = exp4.substring(0, exp4.length() - 4)
+ c[j5]
+ exp4.substring(exp4.length() - 4,
exp4.length());
for (int j6 = 0; j6 < 4; j6++) {
exp6 = exp5.substring(0, exp5.length() - 3)
+ c[j6]
+ exp5.substring(exp5.length() - 3,
exp5.length());
for (int j7 = 0; j7 < 4; j7++) {
exp7 = exp6.substring(0, exp6.length() - 2)
+ c[j7]
+ exp6.substring(exp6.length() - 2,
exp6.length());
for (int j8 = 0; j8 < 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 >= '0' && c1 <= '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+4*56-7-8-9
第2个 exp = 1+2-3*4+5*6*7+8-9
第3个 exp = 1+2*3*45-6+7-8*9
第4个 exp = 1+2*3*45-6-7*8-9
第5个 exp = 1+23+4*5+67+89
第6个 exp = 1+23+45+6*7+89
第7个 exp = 1+23*4+5+6+7+89
第8个 exp = 1+234+5*6+7-8*9
第9个 exp = 1+234+5*6-7*8-9
第10个 exp = 1+234-5+6*7-8*9
第11个 exp = 1+234-5-6-7-8-9
第12个 exp = 1-2+3*45+67+8-9
第13个 exp = 1-2*3+45*6+7-8*9
第14个 exp = 1-2*3+45*6-7*8-9
第15个 exp = 1-2*3-4+5*6*7+8-9
第16个 exp = 1*2+3*45-6+78-9
第17个 exp = 1*2-3+45+67+89
第18个 exp = 1*2-3+45*6-78+9
第19个 exp = 1*23+4*56-7*8+9
第20个 exp = 12+3+4*5*6+7*8+9
第21个 exp = 12+3+4*5*6-7+8*9
第22个 exp = 12+3*45+6+7*8-9
第23个 exp = 12+34*5-6+7+8+9
第24个 exp = 12-3+45*6-7-8*9
第25个 exp = 123+4+5+67-8+9
第26个 exp = 123-4+5-6-7+89

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

Answer 3

遍历所有表达式判断结果

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

Answer 4

可以从分割入手 然后填写符号
例如 先分割
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