recursion - 数学表达式简化 f#

Question

我正在研究一个数学表达式简化器(相当基本，没有指数、对数、根、分数等)，并且我基本上可以使用它。在我使用的 19 项测试中，其中 14 项通过了。对于剩下的 5 个，我在简化函数中编写了多个其他语句，但它似乎没有改变任何事情。

下面是代码(复制并粘贴到解释器中，它工作得很好)

    //expression types 
type Expression =
    | X
    | Y
    | Const of float
    | Neg of Expression
    | Add of Expression * Expression
    | Sub of Expression * Expression
    | Mul of Expression * Expression

// formats string 
let exprToString expr =
    let rec recExprStr parens expr =
        let lParen = if parens then "(" else ""
        let rParen = if parens then ")" else ""
        match expr with
        | X -> "x"
        | Y -> "y"
        | Const n -> n.ToString()
        | Neg e -> lParen + "-" + recExprStr true e + rParen
        | Add (e1, e2) -> lParen + recExprStr true e1 + "+" + recExprStr true e2 + rParen
        | Sub (e1, e2) -> lParen + recExprStr true e1 + "-" + recExprStr true e2 + rParen
        | Mul (e1, e2) -> lParen + recExprStr true e1 + "*" + recExprStr true e2 + rParen
    recExprStr false expr

//simplification function 
let rec simplify expr =
    match expr with
    //addition 
    | Add(Const(ex1), Const(ex2)) -> Const(ex1 + ex2)
    | Add(ex1, Const(0.)) -> ex1 |> simplify
    | Add(Const(0.), ex1) -> ex1 |> simplify
    | Add(Const(num), ex1) -> Add(ex1, Const(num)) |> simplify
    | Add(ex1, Neg(ex2)) -> Sub(ex1, ex2) |> simplify
    | Add(Neg(ex1), ex2) -> Sub(ex2, ex1) |> simplify
    //subtraction 
    | Sub(Const(num1), Const(num2)) -> Const(num1 - num2)
    | Sub(ex1, Const(0.)) -> ex1 |> simplify
    | Sub(Const(0.), ex1) -> Neg(ex1) |> simplify
    //multiplication 
    | Mul(Const(num1), Const(num2)) -> Const(num1 * num2)
    | Mul(ex1, Const(1.)) -> ex1 |> simplify
    | Mul(Const(1.), ex1) -> ex1 |> simplify
    | Mul(ex1, Const(0.)) -> Const(0.)
    | Mul(Const(0.), ex1) -> Const(0.)
    | Mul(ex1, Const(num1)) -> Mul(Const(num1), ex1) |> simplify
    | Mul(Neg(ex1), ex2) -> Neg(Mul(ex1, ex2)) |> simplify
    | Mul(ex1, Neg(ex2)) -> Neg(Mul(ex1, ex2)) |> simplify
    //negation involving a number
    | Neg(Const(0.)) -> Const(0.)
    | Neg(Neg(ex1)) -> ex1 |> simplify
    | _ -> expr

//Tests
printfn "---Provided Tests---"
let t1 = Add (Const 5.0, Const 3.0)
let t2 = Sub (Const 5.0, Const 3.0)
let t3 = Mul (Const 5.0, Const 3.0)
let t4 = Neg (Const 4.0)
let t5 = Neg (Const -9.0)
let t6 = Add (X, Const 0.0)
let t7 = Add (Const 0.0, Y)
let t8 = Sub (X, Const 0.0)
let t9 = Sub (Const 0.0, Y)
let t10 = Sub (Y, Y)
let t11 = Mul (X, Const 0.0)
let t12 = Mul (Const 0.0, Y)
let t13 = Mul (X, Const 1.0)
let t14 = Mul (Const 1.0, Y)
let t15 = Neg (Neg X)
let t16 = Sub (Mul (Const 1.0, X), Add (X, Const 0.0))
let t17 = Add (Mul (Const 4.0, Const 3.0), Sub (Const 11.0, Const 5.0))
let t18 = Sub (Sub (Add (X, Const 1.0), Add (X, Const 1.0)), Add (Y, X))
let t19 = Sub (Const 0.0, Neg (Mul (Const 1.0, X)))

//Output goes here! 
//5 + 3 = 0
printfn "t1  Correct: 8\t\tActual: %s" (exprToString (simplify t1))
//5-3 = 2
printfn "t2  Correct: 2\t\tActual: %s" (exprToString (simplify t2))
//5 * 3 = 15
printfn "t3  Correct: 15\t\tActual: %s" (exprToString (simplify t3))
//-(4) = -4
printfn "t4  Correct: -4\t\tActual: %s" (exprToString (simplify t4))
//-(-9) = 9
printfn "t5  Correct: 9\t\tActual: %s" (exprToString (simplify t5))
//x + 0 = x
printfn "t6  Correct: x\t\tActual: %s" (exprToString (simplify t6))
//0 + y = y
printfn "t7  Correct: y\t\tActual: %s" (exprToString (simplify t7))
//x - 0 = x
printfn "t8  Correct: x\t\tActual: %s" (exprToString (simplify t8))
//0 - y = -y
printfn "t9  Correct: -y\t\tActual: %s" (exprToString (simplify t9))
//y - y = 0
printfn "t10  Correct: 0\t\tActual: %s" (exprToString (simplify t10))
//x * 0 = 0
printfn "t11  Correct: 0\t\tActual: %s" (exprToString (simplify t11))
//0 * y = 0
printfn "t12  Correct: 0\t\tActual: %s" (exprToString (simplify t12))
//x * 1 = x
printfn "t13  Correct: x\t\tActual: %s" (exprToString (simplify t13))
//1 * y = y
printfn "t14  Correct: y\t\tActual: %s" (exprToString (simplify t14))
//-(-x) = x
printfn "t15  Correct: x\t\tActual: %s" (exprToString (simplify t15))
// (1 * x) - (x + 0) = 0
printfn "t16  Correct: 0\t\tActual: %s" (exprToString (simplify t16))
//(4 * 3) + (11 - 5) = 18
printfn "t17  Correct: 18\t\tActual: %s" (exprToString (simplify t17))
// ((x + 1) - (x + 1)) - (y+x) = -y -x
printfn "t18  Correct: -y -x\t\tActual: %s" (exprToString (simplify t18))
// 0 - (-(1 * x)) = x
printfn "t19  Correct: x\t\tActual: %s" (exprToString (simplify t19))
// (x + 1) *  (-2y + x) 

程序的输出如下，我标记了6个失败的测试(正确的是正确答案，实际的是我返回的结果)

t1  Correct: 8          Actual: 8
t2  Correct: 2          Actual: 2
t3  Correct: 15         Actual: 15
t4  Correct: -4         Actual: -4
t5  Correct: 9          Actual: --9 //FAILS 
t6  Correct: x          Actual: x
t7  Correct: y          Actual: y
t8  Correct: x          Actual: x
t9  Correct: -y         Actual: -y
t10  Correct: 0         Actual: y-y //FAILS
t11  Correct: 0         Actual: 0
t12  Correct: 0         Actual: 0
t13  Correct: x         Actual: x
t14  Correct: y         Actual: y
t15  Correct: x         Actual: x
t16  Correct: 0         Actual: (1*x)-(x+0)          //FAILS
t17  Correct: 18                Actual: (4*3)+(11-5) //FAILS
t18  Correct: -(y + x)             Actual: ((x+1)-(x+1))-(y+x) //FAILS 
t19  Correct: x         Actual: x

我对如何解决最后的 4 (16,17,18) 有点困惑，但在我看来，#5 和 #10 应该可行。

对于测试 5，我添加了 | Neg(Neg(ex1)) -> ex1 |> Simply 我认为它会捕获我的双重否定，但没有。

对于测试 10，我想到了类似 | 的东西。 Sub(ex1, ex2) -> (ex1 - ex2) 可以工作，但事实证明这甚至不是有效的语法。

我已经浏览了大约六个有关简化的资源，甚至复制并粘贴了他们的一些工作，我的测试仍然失败。它知道我一定错过了一两个案例，但我正在抓着我的头发试图弄清楚我可能遗漏了什么!我非常感谢任何意见!

(原始帖子有一个测试 20，出于简化答案的目的，我已将其删除。鉴于我当前的代码，我意识到我不可能简化它)

Answer 1

5:Neg(Const -9) 没有得到简化。它不是负数的负数。您需要一个规则 Neg(Const x) -> Const(-x) 来替换 Neg(Const 0.) 规则。

10: Sub(x,y) 当 y = x -> Const(0)

16:你没有简化内部部件。我会在简化外部部件之前这样做。例如。 Sub(x,y) -> 让 x',y' = 简化 x, 简化 y 然后将 x',y' 与...匹配

17:16 的解决方案可以解决此问题。

18:10 和 16 的解决方案可以解决此问题。

我也忍不住建议 let t = [Add (Const 5.0, Const 3.0); Sub (Const 5.0, Const 3.0)...] 然后 t |> List.iteri ... 。

我正在使用一个临时的代数简化器，它的效果还不错，但我想创建一个更严肃的代数简化器。如果有人对这方面的工作非常感兴趣，请告诉我。