数学表达式简化 f#

Question

我正在研究一个数学表达式简化器（相当基础，没有指数、对数、根、分数等），我大部分时间都在使用它。在我使用的 19 个测试中，有 14 个通过了。对于剩下的 5 个，我在我的 simplify 函数中写了多个其他语句，但它似乎没有改变任何事情。

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

    //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 |> simplify，我认为它会捕捉到我的双重否定但没有。

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

我查看了大约六种关于简化的资源，即使复制和粘贴他们的一些工作，我的测试仍然失败。它知道我一定只是遗漏了一两个案例，但我正在努力想弄清楚我可能遗漏了什么！我非常感谢任何输入！

（原来的 post 有一个测试 20，为了简化答案我已经删除了它。鉴于我目前的代码，我意识到我不可能简化它）

Answer 1

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

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

16：你没有简化内部零件。我会在简化外部部件之前这样做。例如。 Sub(x,y) -> let x',y' = simplify x, simplify y 然后 match x',y' with....

17：解决方案 16 可以解决这个问题。

18：解决方案 10 和 16 可以解决这个问题。

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

我正在使用一个特别的代数简化器，它还可以，但我想创建一个更严肃的简化器。如果有人对此感兴趣，请告诉我。

数学表达式简化 f#

Math Expression Simplification f#

recursion

f#

f#-interactive