前言
此篇为《程序员的算法趣题》中的入门篇第二题"数列的四则运算"的相关解题分析博文。
关于该系列的介绍请看：
这篇拖了一个周，之前自己看牙拔牙加上带我妈去医院看病耽误了不少时间，本来应该是上周就要完成的，真是之前才立的一周一篇的 flag 马上就被打脸了，现在脸都还是生疼（拔牙之后的那种疼）。
题目
Q2 数列的四则运算
大家小时候可能也玩过“组合车牌号里的 4 个数字最终得到 10”的游戏。
组合的方法是在各个数字之间插入四则运算的运算符组成算式，然后计算算式的结果（某些数位之间可以没有运算符，但最少要插入 1 个运算符）。
例）
1234 → 1 ＋ 2×3 - 4 ＝ 3
9876 → 9×87 ＋ 6 ＝ 789
假设这里的条件是，组合算式的计算结果为“将原数字各个数位上的数逆序排列得到的数”，并且算式的运算按照四则运算的顺序进行（先乘除，后加减）。
那么位于 100~999，符合条件的有以下几种情况。
351-→-3×51 ＝ 153
621-→-6×21 ＝ 126
886-→-8×86 ＝ 688
问题
求位于 1000~9999，满足上述条件的数。
作者思路及代码实现
解决这个问题时，“计算算式的方法”会影响实现方法。如果要实现的是计算器，那么通常会用到逆波兰表示法，而本题则是使用编程语言内置的功能来实现更为简单。
很多脚本语言都提供了类似 eval 这样的标准函数。譬如用 JavaScript 实现时，可以用代码清单 02.01 解决问题。
（以下为代码清单 02.01）
var op = ["+", "-", "*", "/", ""];
for (i = 1000; i < 10000; i++) {
var c = String(i);
for (j = 0; j < op.length; j++) {
for (k = 0; k < op.length; k++) {
for (l = 0; l < op.length; l++) {
val = c.charAt(3) + op[j] + c.charAt(2) + op[k] + c.charAt(1) + op[l] + c.charAt(0);
if (val.length > 4) { /* 一定要插入1 个运算符 */
if (i == eval(val)) {
console.log(val + " = " + i);
}
}
}
}
}
}
第 10 行中的 eval 就是本题的关键点，接下来只是选择和设置运算符了。虽然有比较深的循环嵌套，但只要确定了位数就没有问题。
基于这样的考虑，如果把代码第 1 行的 op 变量设置成以下值，可以进一步提高程序执行效率。
var op = ["*", ""];
Point
如果用其他语言实现同样逻辑，需要对 0 进行特别处理。例如在 Ruby 中，“以 0 开头的数”会被当作八进制数来处理，因此必须排除以 0 开头的数。此外，也需要排除除数为 0 的情况。
答案
5931（5 * 9 * 31＝ 1395）
Column
本书以 Ruby 为主要语言编写源代码，但也有像本题一样用 JavaScript 实现的情况。凡用 JavaScript 实现时，结果都用 console.log 来输出，这个结果可以用浏览器来确认。用 Mozilla Firefox 浏览器打开加载了 JavaScript 源代码的 HTML 文件，然后打开“开发者”→“Web 控制台”（如果用 Google Chrome 浏览器，则是打开“更多工具”→“开发者工具”），就可以确认代码的执行结果了。
eval 函数的危险性
本题使用了 eval 函数。这个函数在计算算式等场景下非常方便，但 eval 可以做到的事情不止于此。例如，eval 还可以用来执行指令。如果在 Web 应用中直接用 eval 执行用户输入的内容，那么用户可能会输入并让程序执行任意指令，包括不恰当的指令。举个例子，假设存在下面这样的用 PHP 编写的 Web 页面（代码清单 02.02）。
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title> 计算器</title></head>
<body>
<form method="post" action="<?php echo $_SERVER['SCRIPT_NAME'];?>">
<input type="text" name="exp" size="30">
<input type="submit" value=" 计算">
</form>
<div>
<?php
if($_SERVER["REQUEST_METHOD"] == "POST"){
$exp = $_POST["exp"];
eval("echo $exp;");
}
?>
</div>
</body>
</html>
这个页面的功能就是计算表单中输入的类似“1 ＋ 2*3”这样的算式，并且显示结果。正常输入算式的情况当然没有问题，但根据输入内容不同，我们还可以执行 PHP 脚本。
举个例子，如果输入 phpinfo( )，那么 PHP 的版本等信息会被打印出来。从安全的角度来看，这是非常危险的。
自己做的思路及实现
刚看到这个题目，其实一开始自己能想到的也是用 js 中的 eval 来实现，但是因为现在是要用 java 来实现，而 java 中没有类似 eval 功能的函数，所以马上想到的就是用动态编译加动态加载的方式来实现。（正好前段时间学 spring 源码课的时候有看到相关的内容）
然后是解决遍历数字，加入操作符拼接成计算表达式的操作。然后自己动手写代码前先试了下几个数字里面加运算符，也很容易就可以知道，除了加*之外的运算符，根本不可能保持原有数字的位数。所以操作符只需要加入乘法操作符即可，另外还需考虑数字之间不加操作符，将多个数字进行整体化处理的符号。
上面那一段得出只能加*的道理很简单。就假设你是一个 10-99 的十位数，中间只能加一个操作符。除了乘法和加法，不可能进行运算之后的数字还能保持是十位数。然后考虑如果是加法的情况，将一个十位数拆分成两个个位数，通过加法计算，也不可能满足题目的要求。
因为这两个位数相加之后的取值范围是 1-18，能满足是十位数的数字只有 10-18，当中任何一个数，都不可能满足题目的要求。所以对于其他高位的数字也可以套用同样的规律，操作符只需要考虑乘法操作符的情况即可。
下面是动态编译/加载完成的一个类似 Eval 函数的方法，用于计算数学表达式。
/**
* 自定义的实现类似JavaScript中Eval()函数的工具类，但是因为需要返回计算式的运行结果，
* 所以这个函数中传入的str不能是语句运行是void类型的。
* （例如:"System.out.println(\"Hello\")"）
*
* @version V1.0
* @Package: cn.dattyrabbit.programerArithmeticTopic.util
* @author: 丁奕
* @date: 2020-08-26 09:55
**/
public class Eval {
public static Object eval(String str) throws Exception {
StringBuffer sb = new StringBuffer();
sb.append("public class Temp");
sb.append("{");
sb.append(" public Object getObject()");
sb.append(" {");
sb.append(" Object obj = " + str + "return obj;");
sb.append(" }");
sb.append("}");
// 调用自定义类加载器加载编译在内存中class文件
// 说明：这种方式也需要些数据落地写磁盘的
// 为毛一定要落地呢，直接内存里加载不就完了嘛
// 应该也是可以的，它从磁盘读了也是进内存
// 只不过java不允许直接操作内存
// 写jni估计是可以
Class clazz = new MyClassLoader().findClass(sb.toString());
Method method = clazz.getMethod("getObject");
// 通过反射调用方法
return method.invoke(clazz.newInstance());
}
public static void main(String[] args) throws Exception {
Object rval = eval("1+2+3+4;");
System.out.println(rval);
}
}
/**
* 自定义ClassLoader。用于加载动态编译的类
*
* @version V1.0
* @Package: cn.dattyrabbit.programerArithmeticTopic.util
* @author: 丁奕
* @date: 2020-08-28 10:18
**/
public class MyClassLoader extends ClassLoader {
public static final String classPath = System.getProperty("user.dir") + "\\bin\\";
/**
* 自定义的一个加载方法,这样的做法似乎破坏了Java的双亲委派
* @param classFullName
* @return
*/
protected Class customLoadClass(String classFullName){
String filePath = classFullName2FileName(classFullName, classPath);
byte[] data = loadClassFromFS(filePath );
//调用defineClass将一个字节数据转换成一个类并进行初始化工作.
return defineClass(classFullName, data, 0, data.length);
}
/**
* 将一个完整类名转换为一个当前工程classpath为基础的文件路径.
* @param classFullName 一个完整类名
* @param classPath 当前工程类路径
* @return
*/
public String classFullName2FileName(String classFullName, String classPath){
classFullName = classFullName.replaceAll("[.]", "\\\\" );
return classPath + classFullName + ".class";
}
/**
* 从文件系统中加载类文件,生成一个byte[].
* @param filePath 文件路径
* @return 类文件的字节码数组
*/
private byte[] loadClassFromFS(String filePath) {
FileInputStream fis = null;
byte[] byteSource = null;
try {
fis = new FileInputStream(new File(filePath ) );
ByteArrayOutputStream tempSource = new ByteArrayOutputStream();
int readChar = 0;
while ((readChar = fis.read()) != -1) {
tempSource.write(readChar );
}
byteSource = tempSource.toByteArray();
} catch (IOException e) {
//IO出错
e.printStackTrace();
}
return byteSource;
}
@Override
public Class<?> findClass(String str) throws ClassNotFoundException{
JavaCompiler compiler = ToolProvider.getSystemJavaCompiler();
// 内存中的源代码保存在一个从JavaFileObject继承的类中
JavaFileObject file = new JavaSourceFromString("Temp", str);
// System.out.println(file);
Iterable compilationUnits = Arrays.asList(file);
// 需要为compiler.getTask方法指定编译路径：
// 执行过程如下：
// 1、定义类的字符串表示。
// 2、编译类
// 3、加载编译后的类
// 4、实例化并进行调用。
String flag = "-d";
String outDir = System.getProperty("user.dir") + "\\" + "bin";
Iterable<String> stringdir = Arrays.asList(flag, outDir); // 指定-d dir 参数
// 建立一个编译任务
JavaCompiler.CompilationTask task = compiler.getTask(null, null, null,
stringdir, null, compilationUnits);
// 编译源程序
boolean result = task.call();
if (result) {
try {
return customLoadClass( "Temp");
} catch (Exception e) {
throw new ClassNotFoundException("Temp", e);
}
}
return null;
}
}
class JavaSourceFromString extends SimpleJavaFileObject {
private String code;
public JavaSourceFromString(String name, String code) {
super(URI.create("string:///" + name.replace('.', '/')
+ Kind.SOURCE.extension), Kind.SOURCE);
this.code = code;
}
public CharSequence getCharContent(boolean ignoreEncodingErrors) {
return code;
}
}
这样就有一个类似 Eval()的功能可以使用。然后是解题代码的部分
/**
* 《程序员的算法趣题》 - 入门篇 - Q02 - 数列的四则运算
*
* 题目：大家小时候可能也玩过“组合车牌号里的 4 个数字最终得到 10”的游戏。
*
* 组合的方法是在各个数字之间插入四则运算的运算符组成算式，
* 然后计算算式的结果（某些数位之间可以没有运算符，但最少要插入 1 个运算符）。
*
* 例）
*
* 1234 → 1 ＋ 2×3 - 4 ＝ 3
* 9876 → 9×87 ＋ 6 ＝ 789
*
* 假设这里的条件是，组合算式的计算结果为“将原数字各个数位上的数逆序排列得到的数”，
* 并且算式的运算按照四则运算的顺序进行（先乘除，后加减）。
*
* 那么位于 100~999，符合条件的有以下几种情况。
*
* 351-→-3×51 ＝ 153
* 621-→-6×21 ＝ 126
* 886-→-8×86 ＝ 688
*
* 问题
*
* 求位于 1000~9999，满足上述条件的数。
*
* @description 数列的四则运算实现
* 思路：看到这个题目的时候，最初能想到的就是使用JavaScript中的eval()函数来解决是最便捷的。但是因为JAVA没有类似
* 的功能，所以就需要自己来实现一个类似的功能。
*
* 这里我目前能想到的实现eval()函数功能的方式就是使用动态编译和动态加载来完成。所以得先完成实现该功能的相关工具
* 类，然后再在这个类当中去使用工具类的方法，实现类似JavaScript的eval()函数来完成解题。
*
* 然后在已有实现类似eval()函数功能之后，再去遍历1000~9999，然后分别把四则运算的操作数也遍历加入到1000~9999的字
* 符串之中，然后再使用实现的eval()方法来及时运算，获得结果再判断即可。当然这里四则运算的操作书除了基本的加减乘
* 除外还需要多定义一个空符号""，表示不加入操作数，让前后的单个数字连起来作为一个整数计算。
*
* ------------------------
* 使用最初想到动态编译和动态加载的方式有大量的I/O操作，所以性能较低，耗时巨长，后来找了一种使用avaScriptEngine处理的方法，
* 耗时减少很多，但是还是觉得耗时挺长的。最后才另寻方法，换为将计算表达式转化为后缀表达式再计算的方法。时间开销终于
* 降到一个可以接受的范围。
*
* @version V1.0
* @Package: cn.dattyrabbit.programerArithmeticTopic.primer.q2.sequenceArithmetic
* @author: 丁奕
* @date: 2020-08-26 09:37
**/
public class SequenceArithmetic {
//初始化ScriptEngine
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("JavaScript");
/**
* 包装方法，用于调用的时候不传type，给type赋予0的默认处理方式。
* @param min
* @param max
* @return
*/
public ArrayList<Integer> searchTargetNum(int min, int max){
return searchTargetNum(min, max, 0);
}
/**
* 根据传入的最大和最小值来查找其中符合要求的数字
* @param min 最小值，大于等于
* @param max 最大值，小于
* @param type 处理方式: 0|其他 -> 转换为后缀表达式计算;
* 1 -> 使用JavaScriptEngine 中的eval处理
* 2 -> 使用态编译和动态加载处理
* @return
*/
public ArrayList<Integer> searchTargetNum(int min, int max, int type){
//参数验证
if(min >= max){
return (ArrayList)Arrays.asList(-1);
}
//初始化满足的数的list
ArrayList<Integer> targetNum = new ArrayList<>();
//设置遍历的初始值
int num = min;
//定义操作符的数组,空字符暂用_代替，传入eval时替换为空
char options[] = {'_','*'};
//循环遍历
for(; num < max ; num++){
//打印当前验证的数字
System.out.println("正在处理:--- "+ num +" ---数字");
//遍历每个数的时候根据数字转换为字符串，并再遍历操作符，在数字之间插入符号
char operand[] = String.valueOf(num).toCharArray();
//根据当前num的值，计算需要插入的操作符的个数，从而求出操作符的组合数量。遍历改组合数量，化为二进制。
//需要插入的操作符的组合数量就是 (操作符的长度)^(位数 - 1)。因为操作符的长度为2,所以结果是2的N次幂
int operatorNums = (int)Math.pow((double)options.length,(operand.length - 1));
//判断拼接后的字符串，至少插入了一个操作符所以遍历操作符应该从1开始，到operatorNums-1结束。
//0开始则没有添加任何操作符，遍历到operatorNums则操作符会加在数字的外面而不是数字的中间
for(int i = 1; i < operatorNums; i++){
//转换成二进制,且根据需要的位数进行左边补零的操作
String operatorBinary = zeorFill(Integer.toBinaryString(i),operatorNums);
//开始拼接放入eval函数中的语句
String evalStatement = "";
for(int j = operand.length - 1; j >= 0; j--){
evalStatement += operand[j];
//判断是否是最后一个数
if(j != 0){
evalStatement += options[Integer.parseInt(String.valueOf(operatorBinary.charAt(j-1)))];
}
}
//替换_符号。
evalStatement = evalStatement.replaceAll("_","");
//处理evalStatement语句中的各个操作数，使其符合java语法规范。因为出现08*1这样的数字是编译无法通过的。所以要对各操作数进行去除左边的0的操作。
evalStatement = handleStatement(evalStatement);
//加分号
evalStatement += ";";
try{
int check;
if(type == 1){
check = (int) engine.eval(evalStatement);
}else if(type == 2){
check = (int)Eval.eval(evalStatement);
}else{
check = ((Double)Calculator.calculate(evalStatement)).intValue();
}
//若满足条件，放入targetNum中
if(num == check){
targetNum.add(num);
}
}catch (Exception e){
e.printStackTrace();
}
}
}
return targetNum;
}
/**
* 根据传入的待计算语句进行处理，对各个操作数进行去除左边多余的0的操作，使其符合语法规范
* @param evalStatement
* @return
*/
private String handleStatement(String evalStatement) {
String[] operatorNums = evalStatement.split("\\*");
List<String> array = new ArrayList<>();
for (String operatorNum : operatorNums) {
//用字符串转Int再转字符串的操作来去左边的0
array.add(String.valueOf(Integer.parseInt(operatorNum)));
}
String resultStatement = StringUtils.join(array, "*");
return resultStatement;
}
/**
* 根据传入的二进制数（Integer.toBinaryString直接转换的数）和允许的最大的数字进行左边补零的操作，
* @param originalBinary
* @param operatorNums
* @return
*/
private String zeorFill(String originalBinary, int operatorNums) {
String binaryStr = originalBinary;
String maxOperatorNums = Integer.toBinaryString(operatorNums - 1);
while(binaryStr.length() < maxOperatorNums.length()){
binaryStr = "0"+binaryStr;
}
return binaryStr;
}
}
代码里面我已经在写代码前把思路用注释写过一遍，所以为啥写这些方法，每个方法是干啥的。都体现在代码里了。需要多说的就是通过自己的方式实现一遍之后，运行下来非常耗时，因为自己的实现方式有大量的 I/O 操作，所以性能比较不堪，也是正常，所以才有了后面两种其他的处理方式。也就是通过给方法的 type 参数传值来控制具体的处理方式。
然后是写一个测试类，测试类代码如下
/**
* 数列的四则运算测试
*
* @version V1.0
* @Package: primer.q2.sequenceArithmetic
* @author: 丁奕
* @date: 2020-09-01 11:00
**/
public class SequenceArithmeticTest {
public static void main(String[] args) {
long start = System.currentTimeMillis();
SequenceArithmetic sequenceArithmetic = new SequenceArithmetic();
ArrayList<Integer> integers = sequenceArithmetic.searchTargetNum(1000, 9999);
for (Integer integer : integers) {
System.out.println(integer);
}
long end = System.currentTimeMillis();
System.out.println("总共用时：" + (end-start) +"ms");
}
}
这里直接给出三种模式的运行结果图作为对比吧
动态编译/加载的方式实现
这种真的太久了，我都下去取了个快递回来都还没运行完，肯定不能这样做。
使用 ScriptEngine 调用 js 的 eval 实现
这个勉勉强强能接受，但是肯定不够好
使用后缀表达式计算的方式实现
重要找到了一个好的方案，谢天谢地。
这部分使用到的数学表达式转后缀表达式进行计算的代码没贴出来，可以在 git 上查看源码。git 地址在前言的开坑记录中有。这部分实现的参考文章在这里：(参考文章:java 实现运算字符计算)
不同思路的对比
要对比跟作者的不同，这一节可以运行下作者提供的 JS 代码。下图为运行结果，我是直接开了个浏览器，然后再 console 中粘入代码运行的。如下图
看计算时间的话，跟我最后使用的后缀表达的方案没差太多。这一回自己这边尝试了三种实现，说到底还是搞了蛮久的，不过我觉得我在对遍历数字插入计算符的操作上，有不少创新思路，而且把问题更加的泛化了，如果使用作者的方法，那么求 100-99999 中的符合要求的数，就要改代码。而且循环的层数也会有增加。而我自己实现的代码，直接改变参数即可。计算结果如下图
总结
这次的题目，个人觉得实现还是比较满意的，虽然第一时间想到的方案并不是最佳的，但是也尝试实现了出来，并且在不满意结果的同时，又尝试了不同的解决方案，最后一步一步得到了一个相对满意的结果。
当然最后的代码也是不完善的，也还有很多地方可以继续改进优化，不过实现的时候有考虑去泛化问题，使得在后期去比对作者的实现时更具有优势这一点来说，还算是比较满意的。所以平时就算是写业务代码，也尽可能的多考虑考虑之如果有业务变更，怎样做才能在今后做最少的改动。
因为这一篇拖了一周，所以下一篇会尽力尽快在最近两天肝出来先把整体的进度补上，peace🙏 。
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于