Вправа: обчислення виразу

Давайте напишемо простий рекурсивний обчислювач арифметичних виразів.

Прикладом невеликого арифметичного виразу може бути 10 + 20, який обчислюється як 30. Ми можемо представити цей вираз у вигляді дерева:

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

У коді ми будемо представляти дерево двома типами:

#![allow(unused)]
fn main() {
/// Операція для виконання над двома під-виразами.
#[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).

Деякі вирази не можуть бути обчислені і повертають помилку. Стандартний тип Result<Value, String> - це перелік, який представляє або успішне значення (Ok(Value)), або помилку (Err(String)). Ми розглянемо цей тип більш детально пізніше.

Скопіюйте та вставте код у середовище Rust і почніть реалізацію eval. Кінцевий продукт повинен пройти тести. Може бути корисно використати todo!() і змусити тести проходити один за одним. Ви також можете тимчасово оминути тест за допомогою #[ignore]:

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

#![allow(unused)]
fn main() {
/// Операція для виконання над двома під-виразами.
#[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) -> Result<i64, String> {
    todo!()
}

#[test]
fn test_value() {
    assert_eq!(eval(Expression::Value(19)), Ok(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)),
        }),
        Ok(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),
        }),
        Ok(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))
        }),
        Ok(0)
    );
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Mul,
            left: Box::new(Expression::Value(0)),
            right: Box::new(Expression::Value(0))
        }),
        Ok(0)
    );
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Sub,
            left: Box::new(Expression::Value(0)),
            right: Box::new(Expression::Value(0))
        }),
        Ok(0)
    );
}

#[test]
fn test_error() {
    assert_eq!(
        eval(Expression::Op {
            op: Operation::Div,
            left: Box::new(Expression::Value(99)),
            right: Box::new(Expression::Value(0)),
        }),
        Err(String::from("ділення на нуль"))
    );
}
}