Go Deep | Blog

Go Deep and Be professional

0%

Rust-DFS给表达式添加运算符

在某一个信息流网站上,看到一个challenge,里面有部分是编程题。

在Leetcode上有类似的题目,比如Leetcode-282
其要求也同样是给数字填补运算符。

但是它的运算符只有+ - *以及邻接符号(表示两个数字之间不添加任何运算符,自组成一个完整的数字,比如10是1和0组成的数字)。

但是这个challenge则不同,它一共拥有+ - * / % ^6个符号,且无邻接字符。那么它其实又简单了又复杂了。

简单在不需要考虑邻接字符,复杂在运算符变成了6个,且有3中不同的优先级(^优先级最高,表示取次方)。

未见他人有写过这样类似的题目和解答方案,故在此记录一下,便于他人学习。


题目描述

由于该信息流网站的这个challenge是每隔一段时间变化的,可能读者看到这里的时候该challenge又会发生变化。
所以就不贴具体的地址了。看过该challenge的都懂是哪里的信息流。

切入正题:

1
2
3
4
1_2_3_4_5_6_7_8_9=95551487,
每处_填入1个运算符+-*/%^(注意^符号是次方运算,运算规则是先次方运算再乘除再加减),
每个运算符都要用到并且使得等式成立(答案保证唯一),表达式为?
请输入表达式:

题目解法

思路

大体思路

大体的思路可以分为两个流派,一个是使用DFS(深度递归搜索),一个是使用动态规划。

  • DFS方式很常规,只需要到达所需要的层数时,即可满足运算;
  • 动态规划理论上应该是可行的,之前看过其他大佬有提到过。

但是本人实力有限,尚未看到有人这么写过,或许也有leetcode有这样的题目。也许后续自己对动态规划运筹帷幄过后我再来补这个坑。

当下,我主要使用DFS来完成。

困难点

思路大家都知道是使用DFS,但是具体实施起来是比较困难的,在于不同的优先级。

Leetcode-282的实现大概是:每次不管优先级直接计算,
如果遇到更高的优先级即减去被多计算的值即可。

举个例子:对于表达式:1 + 2 * 3而言,先计算1 + 2,计算结果记为sum = 3prev = 2,当扫描到*时发现2其实不应该被加,
那么运算表达式即变为:sum = 3 - prev + prev * 3,那么结果即变为:sum = 3 - 2 + 2 * 3 = 7

但是,对于这个challenge而言,优先级有+ - * / % ^,光是优先级级别就有三个不同的级别,如果放入DFS当中,DFS需要“记忆”的东西就比较复杂了。

那么这种方式可能就不太合适了。这个就是比较困难的点了。

如何解决这个困难点

某天我日常看Rust社区的推送的时候,看到了一个库叫:fasteval

这个库的作用:根据你输入的表达式字符串去运算(eval),即可算出结果。

比如举个使用的例子:

1
2
3
4
5
6
7
8
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的控制台里验证一下:

1
2
3
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的东西都交给库去做了,我们只需要去负责拼接和递归运算符即可。那么这个问题的复杂度就一下就降了下来。

代码实现

废话不多说,直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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
>> 1^2/3*4^5*6^7+8-9
>> 1%2/3*4^5*6^7+8-9

由于题目要求,每个运算符必须被用到一次,那么填上对应的答案即可。

后续

出题人也是花了心血的,如果哪个大侠能在网络的角落里发现我这篇post,希望还是可以自己好好学习一遍😂。不只是通过闯关而已。

End