演習: 式の評価

算術式のためのシンプルな再帰的評価器を書いてみましょう。

小さな算術式の例として 10 + 20 があり、これは 30 に評価されます。この式は木として表現できます。

より大きく複雑な式として (10 * 9) + ((3 - 4) * 5) があり、これは 85 に評価されます。これはさらに大きな木として表現されます。

コードでは、この木を 2 つの型で表現します。

// 著作権 2023 Google LLC
// SPDX-License-Identifier: Apache-2.0

/// An operation to perform on two subexpressions.
#[derive(Debug)]
enum Operation {
    Add,
    Sub,
    Mul,
    Div,
}

/// An expression, in tree form.
#[derive(Debug)]
enum Expression {
    /// An operation on two subexpressions.
    Op { op: Operation, left: Box<Expression>, right: Box<Expression> },

    /// A literal value
    Value(i64),
}

ここでの Box 型はスマートポインタであり、コースの後半で詳しく扱います。式は、テストにあるとおり Box::new で「ボックス化」できます。ボックス化された式を評価するには、デリファレンス演算子 (*) を使って「アンボックス」します: eval(*boxed_expr)。

次のコマンドで新しい Cargo ライブラリプロジェクトを作成してください。

cargo new --lib evaluator

以下のコードを src/lib.rs ファイルにコピー＆ペーストしてください。

次に eval の実装を始めてください。最終的なライブラリがテストに合格することを cargo test で確認してください。todo!() を使い、テストを 1 つずつ通していくとよいでしょう。#[ignore] を使えば、テストを一時的にスキップすることもできます。

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

// 著作権 2023 Google LLC
// SPDX-License-Identifier: Apache-2.0

/// An operation to perform on two subexpressions.
#[derive(Debug)]
enum Operation {
    Add,
    Sub,
    Mul,
    Div,
}

/// An expression, in tree form.
#[derive(Debug)]
enum Expression {
    /// An operation on two subexpressions.
    Op { op: Operation, left: Box<Expression>, right: Box<Expression> },

    /// A literal value
    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
    )
}