Rust-DFS 给表达式添加运算符
在某一个信息流网站上，看到一个 challenge，里面有部分是编程题。在 Leetcode 上有类似的题目，比如 Leetcode-282， 其要求也同样是给数字填补运算符。
但是它的运算符只有+ - * 以及邻接符号（表示两个数字之间不添加任何运算符，自组成一个完整的数字，比如 10 是 1 和 0 组成的数字）。
但是这个 challenge 则不同，它一共拥有+ - * / % ^6 个符号，且无邻接字符。那么它其实又简单了又复杂了。
简单在不需要考虑邻接字符，复杂在运算符变成了 6 个，且有 3 中不同的优先级（^ 优先级最高，表示取次方）。
未见他人有写过这样类似的题目和解答方案，故在此记录一下，便于他人学习。
Table of Contents
题目描述
由于该信息流网站的这个 challenge 是每隔一段时间变化的，可能读者看到这里的时候该 challenge 又会发生变化。 所以就不贴具体的地址了。看过该 challenge 的都懂是哪里的信息流。
切入正题：
1_2_3_4_5_6_7_8_9=95551487,
每处_填入1个运算符+-*/%^(注意^符号是次方运算，运算规则是先次方运算再乘除再加减),
每个运算符都要用到并且使得等式成立(答案保证唯一),表达式为?
请输入表达式:
题目解法
思路
大体思路
大体的思路可以分为两个流派，一个是使用 DFS（深度递归搜索），一个是使用动态规划。
- DFS 方式很常规，只需要到达所需要的层数时，即可满足运算；
- 动态规划理论上应该是可行的，之前看过其他大佬有提到过。
但是本人实力有限，尚未看到有人这么写过，或许也有 leetcode 有这样的题目。也许后续自己对动态规划运筹帷幄过后我再来补这个坑。
当下，我主要使用 DFS 来完成。
困难点
思路大家都知道是使用 DFS，但是具体实施起来是比较困难的，在于不同的优先级。
原 Leetcode-282 的实现大概是：每次不管优先级直接计算， 如果遇到更高的优先级即减去被多计算的值即可。
举个例子：对于表达式：1 + 2 * 3 而言，先计算 1 + 2，计算结果记为 sum = 3，prev = 2，当扫描到* 时发现 2 其实不应该被加，
那么运算表达式即变为：sum = 3 - prev + prev * 3，那么结果即变为：sum = 3 - 2 + 2 * 3 = 7。
但是，对于这个 challenge 而言，优先级有+ - * / % ^，光是优先级级别就有三个不同的级别，如果放入 DFS 当中，DFS 需要“记忆”的东西就比较复杂了。
那么这种方式可能就不太合适了。这个就是比较困难的点了。
如何解决这个困难点
某天我日常看 Rust 社区的推送的时候，看到了一个库叫：fasteval。
这个库的作用：根据你输入的表达式字符串去运算（eval），即可算出结果。
比如举个使用的例子：
fn main() {
// This example doesn't use any variables, so just use an EmptyNamespace:
let mut ns = fasteval::EmptyNamespace;
if let Ok(val) = fasteval::ez_eval("1+2*3+4^5%6", &mut ns) {
assert_eq!(val, 11.0); // 结果的确是11
};
}
在 Lua 的控制台里验证一下：
Lua 5.3.5 Copyright (C) 1994-2018 Lua.org, PUC-Rio
> 1+2*3+4^5%6
11.0
验证通过。
PS1: 如果用 python 的控制台去验证的话，需要改一下运算符才行。或者使用计算器计算也可以
我为什么会想到这个表达式 eval 的库？ 因为阿里巴巴面试的时候，做过类似的题目，当时的想法即是变成字符串，但是计算的部分是我自己去处理的，处理起来比较复杂。 后来发现这个 fasteval 的库后，大喜！
PS2: 其他语言的库应该也是有类似的库的。Rust 都有，其他语言还能没有？不至于不至于
所以现在 heavy-lifting 的东西都交给库去做了，我们只需要去负责拼接和递归运算符即可。那么这个问题的复杂度就一下就降了下来。
代码实现
废话不多说，直接上代码：
use std::iter::FromIterator;
fn main() {
// 下面被注视的4个是用来测试用的，读者有兴趣也可以逐一测试
// add_operators("12", 3);
// add_operators("123", 6);
// add_operators("1234", 2);
// add_operators("352", 5);
add_operators("123456789", 95551487);
}
/// 算法思想：
/// 1. 运算符分为四种：+, -, *, /, %, ^
/// 2. 利用dfs递归去尝试不同种运算符的拼接方式，当运算符达到数目后，即去计算判断是否与sum要求相同
/// 3. 若结果为所要的期望值，则保存结果字符串
fn add_operators(s: &str, sum: i32) {
// 字符串长度是x，那么slot就是最多x-1个
let total_slot = s.len() - 1;
// 运算符集合, 以char形式存储为vector
let mut result = vec!['.'; total_slot];
// 利用递归思想去遍历不同种运算符的匹配
dfs(0, total_slot, &mut result, s, sum);
}
fn dfs(layer: usize, total_layer: usize, result: &mut Vec<char>, num: &str, sum: i32) {
// 如果到顶了，说明可以判断了
if layer >= total_layer {
let eval_string= merge_alternately(num.to_string(), String::from_iter(result.clone()));
let mut ns = fasteval::EmptyNamespace;
if let Ok(var) = fasteval::ez_eval(&eval_string, &mut ns) {
if (var - sum as f64).abs() < f64::EPSILON {
println!(">> {}", eval_string);
}
}
return;
}
// 一共有6个运算符
for i in 0..6 {
result[layer] = match i + 1 {
1 => '+',
2 => '-',
3 => '*',
4 => '/',
5 => '%',
6 => '^',
_ => unreachable!(),
};
dfs(layer + 1, total_layer, result, num, sum);
// restore the origin
result[layer] = '.';
}
}
// 两个字符串交替合并
pub fn merge_alternately(word1: String, word2: String) -> String {
let mut ans = String::new();
let mut i = 0;
let mut j = 0;
while i < word1.len() || j < word2.len() {
if let Some(c) = word1.chars().nth(i) {
ans.push(c);
}
if let Some(c) = word2.chars().nth(i) {
ans.push(c);
}
i += 1;
j += 1;
}
ans
}
运算结果如下：
>> 1^2/3*4^5*6^7+8-9
>> 1%2/3*4^5*6^7+8-9
由于题目要求，每个运算符必须被用到一次，那么填上对应的答案即可。
后续
出题人也是花了心血的，如果哪个大侠能在网络的角落里发现我这篇 post，希望还是可以自己好好学习一遍😂。不只是通过闯关而已。
The End