简化 ocaml 中计算机代数系统的方程式

Question

我你好！我目前正在尝试在 ocaml 中编写一个程序来绘制一个由用户编写的函数。

为此，我正在解析输入，将输入转换为数据结构。我目前正在尝试创建一个 ocaml 函数来最大程度地简化此输入。

例如，x*x - x*x 将化简为 0

这是我的解析器：

%{
    open Function
%}

%token <float> FLOAT
%token <string> VAR
%token COS SIN SQRT EXP LN PUIS
%token PLUS MINUS TIMES DIV
%token LPAR RPAR
%token EOL
%left LPAR RPAR
%left COS SIN SQRT EXP LN
%left PLUS MINUS
%left TIMES DIV
%left PUIS
%type <Function.formel> main
%start main
%%

main:
expr EOL                    {  }
;

expr:
|   FLOAT                       { flt  }
|   VAR                         { var  }
|   FLOAT VAR                   { mul (flt ) (var ) }
|   LPAR expr RPAR              {  }
|   expr TIMES expr             { mul   }
|   expr DIV expr               { div   }
|   expr PLUS expr              { add   }
|   expr MINUS expr             { sub   }
|   expr PUIS expr              { puis   }
|   COS LPAR expr RPAR          { cos  }
|   PLUS expr                   { pos  }
|   MINUS expr                  { neg  }
|   FLOAT COS LPAR expr RPAR    { mul (flt ) (cos ) }
|   SIN LPAR expr RPAR          { sin  }
|   FLOAT SIN LPAR expr RPAR    { mul (flt ) (sin ) }
|   SQRT LPAR expr RPAR         { sqrt  }
|   LN LPAR expr RPAR           { lnp  }
|   EXP LPAR expr RPAR          { expo  }
;

这是我的词法分析器：

{
    open Parser
    exception Eof
}

rule token = parse
  | [' ' '\t']          { token lexbuf }
  | ['\n']              { EOL }
  | ['0'-'9']+ as lxm   { FLOAT (float_of_string lxm) }
  | '+'                 { PLUS }
  | '-'                 { MINUS }
  | '*'                 { TIMES }
  | '/'                 { DIV }
  | '('                 { LPAR }
  | ')'                 { RPAR }
  | '^'                 { PUIS }
  | "cos"               { COS }
  | "sin"               { SIN }
  | "sqrt"              { SQRT }
  | "ln"                { LN }
  | "exp"               { EXP }
  | ['a'-'z']+ as lxm   { VAR (lxm) }
  | eof                 { raise Eof }

我认为我的解析器和词法分析器都不错。

然后，我使用树来存储函数：

type formel =
| Float of float
| Var of string
| Add of formel * formel
| Sub of formel * formel
| Mul of formel * formel
| Div of formel * formel
| Ln of formel
| Cos of formel
| Sin of formel
| Puis of formel * formel
| Sqrt of formel
| Exp of formel

let flt f = Float f
let add e1 e2 = Add (e1, e2)
let sub e1 e2 = Sub (e1, e2)
let mul e1 e2 = Mul (e1, e2)
let div e1 e2 = Div (e1, e2)
let puis e1 e2 = Puis (e1, e2)
let neg e = Mul (Float (-1.), e)
let pos e = Mul (Float 1., e)
let cos e = Cos e
let sin e = Sin e
let var v = Var v
let sqrt e = Sqrt e
let expo e = Exp e
let lnp e = Ln e

这就是我遇到的困难：创建一个函数来简化。

        let rec simplify f =
        let f_simplify = simp f in
        if f_simplify = f 
        then f_simplify 
        else simplify f_simplify
        and simp f = 
        match f with
        | Float f -> Float f
        | Var x -> Var x

        (* 0 + x -> x *)
        | Add (Float 0., f) -> simp f
        (* x + 0 -> x *)
        | Add (f, Float 0.) -> simp f
        (* f1 + f2-> calcul (f1 + f2) *)
        | Add (Float f1, Float f2) -> Float (f1 +. f2)
        (* x + x -> 2 * x *)
        | Add (f, g) when f = g -> simp (Mul (Float 2., simp f))

        (* f1 * x + x -> (f1 + 1) * x *)
        | Add (Mul (Float f1, f), g) when f = g -> simp (Mul (Float (f1 +. 1.), simp f))
        (* x + f1 * x -> (f1 + 1) * x *)
        | Add (f, Mul (Float f1, g)) when f = g -> simp (Mul (Float (f1 +. 1.), simp f))
        (* x * f1 + x -> (f1 + 1) * x *)
        | Add (Mul (f, Float f1), g) when f = g -> simp (Mul (Float (f1 +. 1.), simp f))
        (* x + x * f1 -> (f1 + 1) * x *)
        | Add (f, Mul (g, Float f1)) when f = g -> simp (Mul (Float (f1 +. 1.), simp f))

        (* f1 * x + f2 * x -> (f1 + f2) * x *)
        | Add (Mul (Float f1, f), Mul (Float f2, g)) when f = g -> simp (Mul (Float (f1 +. f2), simp f))
        (* x * f1 + f2 * x -> (f1 + f2) * x *)
        | Add (Mul (f, Float f1), Mul (Float f2, g)) when f = g -> simp (Mul (Float (f1 +. f2), simp f))
        (* f1 * x + x * f2 -> (f1 + f2) * x *)
        | Add (Mul (Float f1, f), Mul (g, Float f2)) when f = g -> simp (Mul (Float (f1 +. f2), simp f))
        (* x * f1 + x * f2 -> (f1 + f2) * x *)
        | Add (Mul (f, Float f1), Mul (g, Float f2)) when f = g -> simp (Mul (Float (f1 +. f2), simp f))

        | Add (f, g) -> Add (simp f, simp g)

        (* 0 - x -> - x *)
        | Sub (Float 0., f) -> simp (Mul (Float (-1.), simp f))
        (* x - 0 -> x *)
        | Sub (f, Float 0.) -> simp f
        (* f1 - f2 -> calcul (f1 - f2) *)
        | Sub (Float f1, Float f2) -> Float (f1 -. f2)
        (* f1 * x + x -> (f1 + 1) * x *)
        | Sub (f, g) when f = g -> Float 0.

        | Sub (f, g) -> Sub (simp f, simp g)

        (* 0 / x -> 0 *)
        | Div (Float 0., f) -> Float 0.
        (* x / 1 -> x *)
        | Div (f, Float 1.) -> simp f
        (* f1 / f2 -> calcul (f1 / f2) *)
        | Div (Float f1, Float f2) -> Float (f1 /. f2)
        (* x / x -> 1 *)
        | Div (f, g) when f = g -> Float 1.

        | Div (f, g) -> Div (simp f, simp g)

        (* 1 * x -> x *)
        | Mul (Float 1., f) -> simp f
        (* x * 1 -> x *)
        | Mul (f, Float 1.) -> simp f
        (* 0 * x -> 0 *)
        | Mul (Float 0., f) -> Float 0.
        (* x * 0 -> 0 *)
        | Mul (f, Float 0.) -> Float 0.
        (* f1 * f2 -> calcul (f1 * f2) *)
        | Mul (Float f1, Float f2) -> Float (f1 *. f2)

        (* x * x -> x ^ 2 *)
        | Mul (f, g) when f = g -> simp (Puis (simp f, Float 2.))
        (* x ^ a * x -> x ^ (a + 1) *)
        | Mul (Puis (f, g), h) when f = h -> Puis (simp f, simp (Add (simp g, Float 1.)))

        (* (f1 * x) * f2 -> (f1 * f2) * x *)
        | Mul (Mul (Float f1, f), Float f2) -> simp (Mul (Float (f1 *. f2), simp f))
        (* f1 * (f2 * x) -> (f1 * f2) * x *)
        | Mul (Float f1, Mul (Float f2, f)) -> simp (Mul (Float (f1 *. f2), simp f))
        (* (x * f1) * f2 -> (f1 * f2) * x *)
        | Mul (Mul (f, Float f1), Float f2) -> simp (Mul (Float (f1 *. f2), simp f))
        (* f1 * (x * f2) -> (f1 * f2) * x *)
        | Mul (Float f1, Mul (f, Float f2)) -> simp (Mul (Float (f1 *. f2), simp f))

        | Mul (f, g) -> Mul (simp f, simp g)

        (* x ^ 0 -> 1 *)
        | Puis (f, Float 0.) -> Float 1.
        (* 0 ^ x -> 0 *)
        | Puis (Float 0., f) -> Float 0.
        (* x ^ 1 -> x *)
        | Puis (f, Float 1.) -> simp f

        | Puis (f, g) -> Puis (simp f, simp g)

        | Ln f -> Ln (simp f)
        | Cos f -> Cos (simp f)
        | Sin f -> Sin (simp f)
        | Sqrt f -> Sqrt (simp f)
        | Exp f -> Exp (simp f)

这是我的问题：对于像 x*x + x*x 这样的简单函数，此函数有效。但是，如果我输入函数：2 + x*x - x*x，则不会进行任何简化。结果是：2 + x^2 - x^2

我不知道如何解决这个问题，我已经用了 3 天了。

我希望一切都清楚，有人可以给我一些提示！祝你有美好的一天！

Answer 1

问题有两个方面：

如果你画出树，你会看到子树不相等。
你以自上而下的方式进行。通常，应该自下而上进行简化（从高到低的优先级，例如 2+x*x+x*x ==> 2+x^2+x^2 ==> 2+2x^2 ）

你的方程是这棵树的：

- : formel = Sub (Add (Float 2., Mul (Var "x", Var "x")), Mul (Var "x", Var "x"))

让我们按照执行顺序：

匹配Sub (f, g) -> Sub (simp f, simp g) 与

f = Add (Float 2., Mul (Var "x", Var "x"))

g = Mul (Var "x", Var "x")
从 (1) 执行 simp f，因此匹配 Add (f, g) -> Add (simp f, simp g)

2.1。它匹配 Float(2.) 和 Float f -> Float f

2.2。它匹配 Mul(Var("x"),Var("x")) 和 Mul (f, g) when f = g -> simp (Puis (simp f, Float 2.))
它在 simp g 上继续，因此匹配 Mul (f, g) when f = g -> simp (Puis (simp f, Float 2.))

这就是您得到以下结果的原因：

Sub (Add (Float 2., Puis (Var "x", Float 2.)), Puis (Var "x", Float 2.))

(2 + x^2 - x^2)

因为左（2 + x^2）和右（x^2）子树不相等。

解决问题(1)

一个想法是添加可交换的属性加法规则并将其转换为相同优先级的列表。例如，

Sub(f,Add(g,h)) -> [Plus(f),Minus(g),Minus(h)]

用这个你可以识别相同的子树并消除它们。

解决问题(2) 您需要根据运算符的优先级进行简化，例如在 x+x 简化为 2x 之前，x*x 变为 x^2。这可以通过将代码更改为运行多次解析来完成。每次子树发生变化时，重新运行上层树的简化。

另一个想法是通过统一和替换技术将其存档。我还没想好。但这很有说服力。

简化 ocaml 中计算机代数系统的方程式

Simplify equations for a computer algebric system in ocaml

ocaml

symbolic-math