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

19 5月 2021
6 分钟阅读
标签:
rust,
algorithm,
leetcode

更新于 19 5月 2021

题目描述

由于该信息流网站的这个 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，希望还是可以自己好好学习一遍😂。不只是通过闯关而已。