Упражнение: Вычисление выражения

Напишем простой рекурсивный вычислитель арифметических выражений.

Пример небольшого арифметического выражения — 10 + 20, которое вычисляется в 30. Выражение можно представить как дерево:

Более крупное и сложное выражение — (10 * 9) + ((3 - 4) * 5), которое вычисляется в 85. Мы представим его гораздо большим деревом:

В коде мы представим дерево двумя типами:

// 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 через Box::new, как показано в тестах. Чтобы вычислить упакованное выражение, используйте оператор разыменования (*), чтобы «распаковать» его: eval(*boxed_expr).

Создайте новый проект Cargo типа library с помощью

cargo new --lib evaluator

Скопируйте и вставьте код ниже в файл src/lib.rs.

Затем начните реализовывать eval. Используйте cargo test, чтобы убедиться, что итоговая библиотека проходит тесты. Может быть полезно использовать todo!() и добиваться прохождения тестов по одному. Тест можно временно пропустить с помощью #[ignore]:

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

// 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
    )
}