How to Implement Expression Evaluation in Rust for a CAS System?

I've been working on a project to create a Computer Algebra System (CAS) in Rust. My goal is to build something similar to CAS systems available in C, C++, and Python with the added twist of describing the steps to a human much like this library which I found later on, during the creating of my idea. But that feature isn't the problem.
There is another similar CAS Crate in rust however it's not been updated in 3 years and is not documented

In C, C++, and Python, there are established CAS systems (which I can't make heads or tails of), but in Rust, I'm a bit lost on how to proceed. Traditional expression trees use nodes , however in Rust often enums are used for the same thing.

Now, I've managed to create a Term struct that handles expressions like 4x^6 * 7xyz and all the other arithmetic operations like + - * / (with other basic things like TryFrom<&str> or std::fmt::Display) and produces the correct output.

/// Represents a collection of variables, each associated with a numerical value.
/// The `Variables` type is an alias for `BTreeMap<char, Number>`.
pub type Variables = BTreeMap<char,num_notation::Number>;

/// A struct representing a mathematical term.
///
/// A `Term` is a basic unit in a mathematical expression. It consists of a coefficient and variables represented as `BTreeMap<char,Number>` .
#[derive(Debug,PartialEq,Clone)]
pub struct Term {
    /// The coefficient of the term.
    coefficient: num_notation::Number,

    /// The variables and their exponents in the term.
    variables :  Variables,
}
// ...

However, I'm struggling with the next step : how to perform expression operations on these terms with algebra (with only numbers its quite easy :grinning:).
Note : I should mention that I've previously attempted a similar project in C++, but the implementation is far from ideal. It relies on lists and lacks the extendability, maintainability, speed and accuracy I'm aiming for in my Rust project

So basically I've started with something like this:

/// An enum representing a mathematical expression.
///
/// The `Expression` enum allows building complex mathematical expressions
#[derive(Debug)]
pub enum Expression {
    /// Represents a basic unit in a mathematical expression.
    Term(Term),

    /// Represents the addition of two terms.
    ///
    /// The `Plus` variant is a binary operator (+) that takes two `Term` values as its operands.
    Plus(Box<Expression>,Box<Expression>),

    /// Represents the subtraction of two terms.
    ///
    /// The `Minus` variant is a binary operator (-) that takes two `Term` values as its operands.
    Minus(Box<Expression>,Box<Expression>),

    /// Represents the multiplication of two terms.
    ///
    /// The `Mal` variant is a binary operator (*) that takes two `Term` values as its operands.
    Mal(Box<Expression>,Box<Expression>),

    /// Represents the division of two terms.
    ///
    /// The `Durch` variant is a binary operator (/) that takes two `Term` values as its operands.
    Durch(Box<Expression>,Box<Expression>),

    /// Represents a more complex expression that contains nested expressions that contain `()` 
    Nested(Box<Expression>),
}

I have created some utilitiy functions for this

impl Expression {
    /// Create a new `Expression` containing a single `Term`.
    ///
    /// The `new_term` function wraps the provided `Term` into an `Expression::Term` variant.
    pub fn new_term(term: Term) -> Self {
        Expression::Term(term)
    }

    /// Create a new `Expression` representing the addition of two expressions.
    ///
    /// The `new_plus` function constructs an `Expression` with the `Expression::Plus` variant,
    /// combining two expressions as operands in an addition operation (`+`).
    pub fn new_plus(left: Expression, right: Expression) -> Self {
        Expression::Plus(Box::new(left), Box::new(right))
    }

    /// Create a new `Expression` representing the subtraction of two expressions.
    ///
    /// The `new_minus` function constructs an `Expression` with the `Expression::Minus` variant,
    /// combining two expressions as operands in a subtraction operation (`-`).
    pub fn new_minus(left: Expression, right: Expression) -> Self {
        Expression::Minus(Box::new(left), Box::new(right))
    }

    /// Create a new `Expression` representing the multiplication of two expressions.
    ///
    /// The `new_mal` function constructs an `Expression` with the `Expression::Mal` variant,
    /// combining two expressions as operands in a multiplication operation (`*`).
    pub fn new_mal(left: Expression, right: Expression) -> Self {
        Expression::Mal(Box::new(left), Box::new(right))
    }

    /// Create a new `Expression` representing the division of two expressions.
    ///
    /// The `new_durch` function constructs an `Expression` with the `Expression::Durch` variant,
    /// combining two expressions as operands in a division operation (`/`).
    pub fn new_durch(left: Expression, right: Expression) -> Self {
        Expression::Durch(Box::new(left), Box::new(right))
    }
}

For evalutation I believe something like tihs could be used

impl Expression {
/// Evaluates the expression and returns the result as a new `Expression`.
    ///
    /// This function recursively evaluates the expression tree and returns the result
    /// as a new `Expression`. The evaluation process takes into account the values
    /// of any variables that are present in the expression. If the expression contains
    /// nested expressions, they will be evaluated as well.
    pub fn evaluate(&self) -> Self {
        match self {
            Expression::Plus(left, right) => left.clone() + right.clone(),
            Expression::Minus(left, right) => left.clone() - right.clone(),
            Expression::Mal(left, right) => left.clone() * right.clone(),
            Expression::Durch(left, right) => left.clone() / right.clone(),
            Expression::Term(term) => Expression::Term(term.clone()),
           // mostly would not work correctly
            Expression::Nested(inner) => inner.evaluate()
        }
    }
}

However this requires + - * / between the expressions , and I can't seem to find any 'tutorials' or resources for this. But I'm uncertain about how to implement the evaluation of complex expressions and handle operations between them.

If anyone has experience with building CAS systems or has insights into how I can implement arithmetic operations on expression with algebra in Rust, I would greatly appreciate your guidance and suggestions!

Thank you in advance for your help!

You need to evaluate both sides of a binary expression before actually performing it's operation.
Recurse depth-first until you hit something that evaluates to itself, ie: a number.

Expression::Plus(left, right) => left.evaluate() + right.evaluate(),
2 Likes

Yes , I have suggested something like that above. But the question is what exactly is the implementation of + and other operators ?

Well I guess evaluate shouldn't return a Self but a type that represents a result of an operation.
Also shouldn't you also have types like Int and Float etc? Otherwise you cannot determine if a Plus expression is valid if the left and right don't have the same type

Yes the number enum I have made in term (or add num-notation = "0.1.0" to cargo.toml

Well I guess evaluate shouldn't return a Self but a type that represents a result of an operation

Why a result , as we know the expression will be always valid

Well what do you want your thing to evaluate to in the end?

Expression::Term(term) => Expression::Term(term.clone()),

Should it be a term?

I'd like it to evaluate the expressions '2x+8' add '7x + y' into '9x +y+8' ( in any order is fine I think) where something like '4x' is a 'Term' struct I have given above which can add +-*/ with other terms

Well I'm.not sure , maybe. it depends on the exact implementation of the evaluate function. but I thing that could be valid

Well then Add and the other operators becomes potentially a bit wordy because you have to handle all cases in the same Add implementation because everything is an Expression.

If I auto-generate all the needed combinations you get this

impl std::ops::Add for Expression {
    type Output = Expression;

    fn add(self, rhs: Self) -> Self::Output {
        match (self, rhs) {
            (Expression::Term(_), Expression::Term(_)) => todo!(),
            (Expression::Term(_), Expression::Plus(_, _)) => todo!(),
            (Expression::Term(_), Expression::Minus(_, _)) => todo!(),
            (Expression::Term(_), Expression::Mal(_, _)) => todo!(),
            (Expression::Term(_), Expression::Durch(_, _)) => todo!(),
            (Expression::Term(_), Expression::Nested(_)) => todo!(),
            (Expression::Plus(_, _), Expression::Term(_)) => todo!(),
            (Expression::Plus(_, _), Expression::Plus(_, _)) => todo!(),
            (Expression::Plus(_, _), Expression::Minus(_, _)) => todo!(),
            (Expression::Plus(_, _), Expression::Mal(_, _)) => todo!(),
            (Expression::Plus(_, _), Expression::Durch(_, _)) => todo!(),
            (Expression::Plus(_, _), Expression::Nested(_)) => todo!(),
            (Expression::Minus(_, _), Expression::Term(_)) => todo!(),
            (Expression::Minus(_, _), Expression::Plus(_, _)) => todo!(),
            (Expression::Minus(_, _), Expression::Minus(_, _)) => todo!(),
            (Expression::Minus(_, _), Expression::Mal(_, _)) => todo!(),
            (Expression::Minus(_, _), Expression::Durch(_, _)) => todo!(),
            (Expression::Minus(_, _), Expression::Nested(_)) => todo!(),
            (Expression::Mal(_, _), Expression::Term(_)) => todo!(),
            (Expression::Mal(_, _), Expression::Plus(_, _)) => todo!(),
            (Expression::Mal(_, _), Expression::Minus(_, _)) => todo!(),
            (Expression::Mal(_, _), Expression::Mal(_, _)) => todo!(),
            (Expression::Mal(_, _), Expression::Durch(_, _)) => todo!(),
            (Expression::Mal(_, _), Expression::Nested(_)) => todo!(),
            (Expression::Durch(_, _), Expression::Term(_)) => todo!(),
            (Expression::Durch(_, _), Expression::Plus(_, _)) => todo!(),
            (Expression::Durch(_, _), Expression::Minus(_, _)) => todo!(),
            (Expression::Durch(_, _), Expression::Mal(_, _)) => todo!(),
            (Expression::Durch(_, _), Expression::Durch(_, _)) => todo!(),
            (Expression::Durch(_, _), Expression::Nested(_)) => todo!(),
            (Expression::Nested(_), Expression::Term(_)) => todo!(),
            (Expression::Nested(_), Expression::Plus(_, _)) => todo!(),
            (Expression::Nested(_), Expression::Minus(_, _)) => todo!(),
            (Expression::Nested(_), Expression::Mal(_, _)) => todo!(),
            (Expression::Nested(_), Expression::Durch(_, _)) => todo!(),
            (Expression::Nested(_), Expression::Nested(_)) => todo!(),
        }
    }
}

Although you could probably condense them like the following:

impl std::ops::Add for Expression {
    type Output = Expression;

    fn add(self, rhs: Self) -> Self::Output {
        match (self, rhs) {
            (Expression::Term(_), Expression::Term(_)) => todo!(), // Implement adding two terms
            (not_term, other @ Expression::Term(_)) => not_term.evaluate() + other,
            (self_ @ Expression::Term(_), not_term) => self_ + not_term.evaluate(),
            (not_term1, not_term2) => not_term1.evaluate() + not_term2.evaluate(),
        }
    }
}

I haven't fully thought this through though.

Note that I didn't include how to actually add two terms. I guess it would involve some matching of variable names and powers. Also you need to consider if

x + 2y

Should be one or two terms. Your notation of calling it Term.variables seems to suggest that this would be one term which I guess makes sense, but mathematically is wrong as this would be 2 terms.
If I understand correctly you want something like

[1][x] + [2][y] -> [1, 2][x, y]
i.e.
Add(Term(coefficients=[1], variables=['x']), Term(coefficients=[2], variables['y']) -> Term(coefficients=[1, 2], variables=['x', 'y'])

So maybe you just need a different name than Term. Maybe polynome if you just want to handle polynomes. Or just Simplified, as it it already is in simplified version? Also note that in this way it should be Term.coefficients in the plural, i.e. an array or Vec of coefficients.

OR
Do you want

[1][x] + [2][y] -> [1][x] + [2][y]
and
[1][x] + [2][x] -> [3][x]

?
(with the same notation as above, i.e. the first one stays an Expression::Add while the second one turns the Expression::Add into an Expression::Term.)

In this case the name Term totally makes sense. But I guess it becomes quite hard to figure out if two Expressions contain terms of the same variable with the same power because not everything gets reduced into an Expression::Term.

This operation might be better understood as an expression simplifier or normalizer rather than an evaluator. That is, it takes arbitrary expressions and returns expressions in a subset, rather than taking expressions and producing values (a different type).

5 Likes

I already implemented the + - * / with the Term struct so things like 5x^5y + 10y^2x* are correctly operated on (note I have tested this).

I've chosen the "Term" naming convention for simplicity (avoiding new structs and unneeded complications) and familiarity, but I'll keep your idea in mind for the future

So basically for the first example the 'code' will just return self while for the second it will 'combine' them together

  pub(super) fn add(t1 : Term,t2 : Term) -> Expression {
        if t1.variables == t2.variables {
            let coefficient = t1.coefficient + t2.coefficient;
            let variables = t1.variables;
            return Expression::new_term(Term::new_with_variable(coefficient,variables));
        }
        Expression::new_plus(t1.into(),t2.into())
    }

I have made some progress in the general direction for at least addition and subtraction, I can handle x + x - 1 into 2x which isn't correct and I can't figure out how to fix this issue
But it's still some progress using

Please ignore any possible code inefficiencies, comments, and unnecessary elements.

impl Expression {
    fn search_matching_term(&self,target : &Term,on_found : impl Fn(&Term) -> Expression + Clone) -> Option<Expression> {
        match self {
            // stop searching just expression can't be operated on like (..) , (yes ik its not true and a limitation but thats a problem for later)
            Expression::Nested(_) => None,
            Expression::Term(term) => match term == target {
                true => Some(on_found(term)),
                false => Some(self.clone())
            },
            Expression::Plus(right, left)
            | Expression::Minus(right, left)
            | Expression::Mal(right, left)
            | Expression::Durch(right, left) => {
                // Try searching in the right subtree first
                if let Some(expression) = right.search_matching_term(target,on_found.clone()) {
                    // If found in the right subtree, add the current node to the path and return it
                    return Some(expression);
                }

                // If not found in the left subtree, try searching in the left subtree
                if let Some(expression) = left.search_matching_term(target,on_found) {
                    // If found in the left subtree, add the current node to the path and return it
                    return Some(expression);
                }

                // If not found in either subtree, return right operation left
                None
            }
        }
    }
}

And a test for it showing the issue

    // Helper function to create a Term with a single variable.
    fn create_term_with_variable(coeff: f64, var: char, exp: f64) -> Term {
        let mut variables = Variables::new();
        variables.insert(var, Number::Decimal(exp));
        Term::new_with_variable(Number::Decimal(coeff), variables)
    }

 #[test]
    fn test_search_matching_term_with_term_a() {
        // Create a sample expression tree for testing
        let term_a = create_term_with_variable(1.0,'x',1.0); // Define your Term here

        // Build the expression tree
        let expression_tree = Expression::new_plus(
            Expression::new_term(term_a.clone()),
            Expression::new_minus(
                Expression::new_term(term_a.clone()), // Another Term for the right subtree
                Expression::new_nested(Expression::Term(Term::new(Number::Decimal(1.0)))), // Nested Term
            ),
        );

        // aka x + x - (1)
        // or in a more 'tree' form x plus x - (1) 
        assert_eq!(&expression_tree.to_string(),"x + x - (1)");

        // Define a closure to test the search_matching_term function
        let on_found = |term : &Term| {
            term.clone() + term_a.clone()
        };

        let result = expression_tree.search_matching_term(&term_a, on_found);

        // Test case for searching for term_a
        assert_eq!(result.is_some(),true);

        // check if result correct
        // 2x - 1
        let expected = Expression::new_minus(
            create_term_with_variable(2.0,'x',1.0).into(),
            Term::new(Number::Decimal(1.0)).into()
        );
       // result is Some(2x) but expected is Some(2x - 1) , can't figure out how to fix this issue
        assert_eq!(result,Some(expected));
    }

Thinking about it, I might as well share my repository link. Anyone interested in tackling this challenge can access all the necessary code there. Here's the link

There are a few problems. The first is that left and right are swapped in the patterns for Plus, Minus, etc. The second issue is that you are evaluating only one branch and throwing the other away. The third is that Nested isn't handled at all.

The biggest problem is the second one. You need recurse into both sides, ultimately. If you fix the other two issues, you'll see the actual value is evaluated to Some(1) instead of Some(2x). And that's because the right-most leaf evaluates to Some(1). All left branches are ignored.

I will try to figure 1 and 3. but for 2. I am not really sure how do handle this.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.