2.6 练习：表达式求值

练习：表达式求值 — Comprehensive Rust

2 分钟阅读

译文 · 基于 Comprehensive Rust

原文链接: https://google.github.io/comprehensive-rust/pattern-matching/exercise.html

2.6 练习：表达式求值

让我们为算术表达式写一个简单的递归求值器。

一个小算术表达式的例子是 10 + 20，求值为 30。可以把表达式表示成树：

            .-------.
    .------ |   +   | ------.
    |       '-------'       |
    v                       v
.--------.              .--------.
|   10   |              |   20   |
'--------'              '--------'

更大更复杂的表达式可以是 (10 * 9) + ((3 - 4) * 5)，求值为 85。我们把它表示成更大的树：

                              .-----.
            .---------------- |  +  | ----------------.
            |                 '-----'                 |
            v                                         v
         .-----.                                   .-----.
   .---- |  *  | ----.                       .---- |  *  | ----.
   |     '-----'     |                       |     '-----'     |
   v                 v                       v                 v
.------.          .-----.                 .-----.           .-----.
|  10  |          |  9  |           .---- |  "-"| ----.     |  5  |
'------'          '-----'           |     '-----'     |     '-----'
                                    v                 v
                                 .-----.           .-----.
                                 |  3  |           |  4  |
                                 '-----'           '-----'

在代码中，我们用两种类型表示这棵树：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// Copyright 2023 Google LLC
// SPDX-License-Identifier: Apache-2.0
/// 对两个子表达式执行的运算。
#[derive(Debug)]
enum Operation {
    Add,
    Sub,
    Mul,
    Div,
}

/// 树形结构的表达式。
#[derive(Debug)]
enum Expression {
    /// 对两个子表达式的运算。
    Op { op: Operation, left: Box<Expression>, right: Box<Expression> },

    /// 字面量值
    Value(i64),
}

这里的 Box 类型是智能指针，课程后面会详细介绍。可以用测试中看到的 Box::new 把表达式「装箱」。要求值已装箱的表达式，用解引用运算符（*）「拆箱」：eval(*boxed_expr)。

用下面命令新建一个 Cargo 库项目：

1
cargo new --lib evaluator

把下面的代码复制粘贴到 src/lib.rs 文件中。

然后开始实现 eval。用 cargo test 确保最终库通过测试。可以借助 todo!() 让测试逐个通过。也可以用 #[ignore] 暂时跳过某个测试：

#[test]
#[ignore]
fn test_value() { .. }

  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
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
// Copyright 2023 Google LLC
// SPDX-License-Identifier: Apache-2.0
/// 对两个子表达式执行的运算。
#[derive(Debug)]
enum Operation {
    Add,
    Sub,
    Mul,
    Div,
}

/// 树形结构的表达式。
#[derive(Debug)]
enum Expression {
    /// 对两个子表达式的运算。
    Op { op: Operation, left: Box<Expression>, right: Box<Expression> },

    /// 字面量值
    Value(i64),
}

fn eval(e: Expression) -> i64 {
    todo!()
}

#[test]
fn test_value() {
    assert_eq!(eval(Expression::Value(19)), 19);
}

#[test]
fn test_sum() {
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Add,
            left: Box::new(Expression::Value(10)),
            right: Box::new(Expression::Value(20)),
        }),
        30
    );
}

#[test]
fn test_recursion() {
    let term1 = Expression::Op {
        op: Operation::Mul,
        left: Box::new(Expression::Value(10)),
        right: Box::new(Expression::Value(9)),
    };
    let term2 = Expression::Op {
        op: Operation::Mul,
        left: Box::new(Expression::Op {
            op: Operation::Sub,
            left: Box::new(Expression::Value(3)),
            right: Box::new(Expression::Value(4)),
        }),
        right: Box::new(Expression::Value(5)),
    };
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Add,
            left: Box::new(term1),
            right: Box::new(term2),
        }),
        85
    );
}

#[test]
fn test_zeros() {
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Add,
            left: Box::new(Expression::Value(0)),
            right: Box::new(Expression::Value(0))
        }),
        0
    );
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Mul,
            left: Box::new(Expression::Value(0)),
            right: Box::new(Expression::Value(0))
        }),
        0
    );
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Sub,
            left: Box::new(Expression::Value(0)),
            right: Box::new(Expression::Value(0))
        }),
        0
    );
}

#[test]
fn test_div() {
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Div,
            left: Box::new(Expression::Value(10)),
            right: Box::new(Expression::Value(2)),
        }),
        5
    )
}

2.6.1 解答

01-解答 — Comprehensive Rust

最后修改 August 11, 2026: 更新 (70a5af133)