锈蚀中数学表达式的建模

Question

我一直在努力想出一个数据模型，它适用于Rust中的数学表达式(如x^2 +2x-y* 4，无等号)。它和我最熟悉的其他语言很不一样。

最终，我希望能够

我认为数学表达式是递归结构。就像在BNF

<expr> ::= <sum> | <product> | <reciprocal> | <number> | <variable>
<sum> ::= <expr> "+" <expr>
<product> ::= <expr> "*" <expr>
<reciprocal> ::= "1/" <expr>
<power> ::= <expr> "^" <expr>
<number> ::= ...|-4|-3|-2|-1|0|1|2|3|4|...
<variable> ::= "x" | "y" | "any string literal" | ...

首先，建立一个递归的数据结构对我来说很困难。也许enums是正确的选择，也许这个概念对于铁锈来说是完全错误的方法。

我也为借贷、取消引用、所有权等问题而苦苦挣扎。

请让我知道你对我写的代码的看法，我所采取的方法，以及它对我这个计划的野心有多大的适应性，以及你对帮助我进入锈顶空间的任何建议。

use std::collections::BTreeSet;
use std::fmt;

#[derive(Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Clone)]
enum Expression {
    Sum(BTreeSet<(usize, Expression)>),
    Product(BTreeSet<(usize, Expression)>),
    Negation(Box<Expression>),
    Reciprocal(Box<Expression>),
    Power(Box<Expression>, Box<Expression>),
    Variable(Box<str>),
    Number(isize),
}

use Expression::*;

impl fmt::Display for Expression {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Sum(summands) => {
                let mut flat_summands: Vec<String> = vec![];
                for (n, expr) in summands.iter() {
                    let stringified_expr = expr.to_string();
                    for _ in 0..*n {
                        flat_summands.push(format!("{}", stringified_expr));
                    }
                }
                fmt.write_str(&flat_summands.into_iter().map(|summand| summand.to_string()).collect::<Vec<_>>().join(" + "))
            },
            Product(factors) => {
                let mut flat_factors: Vec<String> = vec![];
                for (n, expr) in factors.iter() {
                    let stringified_expr = expr.to_string();
                    for _ in 0..*n {
                        flat_factors.push(format!("{}", stringified_expr));
                    }
                }
                fmt.write_str(&flat_factors.into_iter().map(|factor| factor.to_string()).collect::<Vec<_>>().join(" * "))
            },
            Reciprocal(ref expr) => fmt.write_fmt(format_args!("1 / {}", expr.to_string())),
            Power(ref base, ref exponent) => fmt.write_fmt(format_args!("{} ^ {}", base.to_string(), exponent.to_string())),
            Negation(ref expr) => fmt.write_fmt(format_args!("-{}", expr.to_string())),
            Variable(ref name) => fmt.write_fmt(format_args!("{}", name)),
            Number(n) => fmt.write_fmt(format_args!("{}", n)),
        }
    }
}

fn main() {
    let expr = Sum(BTreeSet::from([(1, Number(1)), (1, Product(BTreeSet::from([(1, Number(2)), (1, Variable(Box::from("x")))])))]));
    println!("{:?}", expr);
    println!("{}", expr);
    assert_eq!(format!("{}", expr), String::from("x * 2 + 1"));
}

我已经提出了Sum和Product集的(count, expr)对的参数，这样以后的数学操作，如将x+x简化为5x，或者x*y*z/ y，将更容易(而不是必须搜索深度嵌套的树以获得等效表达式)。

Answer 1

首先:始终运行cargo clippy和cargo fmt！Clippy通常非常有用，在这种情况下，它会在代码中发现几个错误。这两个命令都将帮助您养成编写惯用和惯用格式的Rust代码的习惯。

您为表达式导出了PartialOrd和Ord。你确定这有道理吗？比较两个排序表达式是什么意思？

我不太喜欢选择Sum和Product BTreeSets。你不会利用它们是集合的事实，因为你不需要比较两个(usize, Expression)值是否相等。实际上，您真正想要的是匹配相同表达式的术语，而不是同一个值和表达式的对，以组合这些术语。因此，使用以下代码是有意义的：HashMap<Expression, usize>。

另一种设计选择是使用规范化表达式的概念。如果您有规范化表达式，那么不仅可以强制将像x + x + x这样的表达式收集到3 * x中，而且可以通过加法(例如3 x + 3y而不是3 ( x + y))分配乘法。

有多种方法可以做到这一点，但最简单的方法是坚持Sum和Product是二进制的，然后有一个normalize函数将和积重写到适当的表单。所以：

enum Expression {
    Sum(Box<Expression>, Box<Expression>),
    Product(Box<Expression>, Box<Expression>),
    // ...
}

fn normalize(e: Expression) -> Expression

或

fn normalize(e: &mut Expression)

甚至使用包装器类型：

struct Normalized(Expression);
fn normalize(e: Expression) -> NormalizedExpression

关键是这样可以更容易地执行不变量，而且可能更有效率。如果要强制表达式具有5 x + 6 y + 7z表单，则需要确保表达式已规范化为Sum(Prod(5, x), Sum(Prod(6, y), Prod(7, z)))。要执行此操作，您必须确保：(1) Sum只关联于从左到右，因此您将Sum(Sum(a, b), c))重写为Sum(a, Sum(b, c))；(2)以某种规范顺序编写术语(我猜从x到y到z，所以按字母顺序排列)；和(3)每个术语都是一个常数乘以一个表达式。

您还可以将规范化表达式的数据模型更改为不同的数据模型，例如使用HashMap<Expression, usize>存储每个表达式的常量计数。