OCaml多项式表达式化简函数失效问题求助

问题分析 #

现有simplify函数仅实现了基础常数运算和0项消除，核心的乘法展开、同类项合并、次数排序逻辑完全缺失，无法将表达式转换为标准多项式形式。

修正后的完整代码 #

open Ast
open ExpressionLibrary

(* 用关联列表表示多项式：(次数, 系数)，次数为int，系数为float *)
type polynomial = (int * float) list

(* 合并同类项：将相同次数的系数相加，返回按次数降序排列的多项式，过滤系数为0的项 *)
let merge_like_terms (poly : polynomial) : polynomial =
  let rec merge acc = function
    | [] -> acc
    | (deg, coeff) :: rest ->
        let existing = List.assoc_opt deg acc in
        let new_coeff = match existing with
          | Some c -> c +. coeff
          | None -> coeff
        in
        let acc' = List.remove_assoc deg acc @ [(deg, new_coeff)] in
        merge acc' rest
  in
  poly
  |> merge []
  |> List.filter (fun (_, c) -> c <> 0.)
  |> List.sort (fun (d1, _) (d2, _) -> compare d2 d1)

(* 将表达式转换为多项式形式 *)
let rec expr_to_poly (e : expression) : polynomial =
  match e with
  | Num n -> [(0, n)]
  | Var -> [(1, 1.)]
  | Binop (Add, e1, e2) -> expr_to_poly e1 @ expr_to_poly e2
  | Binop (Sub, e1, e2) -> 
      expr_to_poly e1 @ List.map (fun (d, c) -> (d, -.c)) (expr_to_poly e2)
  | Binop (Mul, e1, e2) ->
      let p1 = expr_to_poly e1 in
      let p2 = expr_to_poly e2 in
      (* 多项式乘法：(a*x^d1) * (b*x^d2) = (a*b)*x^(d1+d2) *)
      List.concat (List.map (fun (d1, c1) -> List.map (fun (d2, c2) -> (d1 + d2, c1 *. c2)) p2) p1)

(* 将多项式转换回AST表达式 *)
let poly_to_expr (poly : polynomial) : expression =
  match poly with
  | [] -> Num 0.
  | [(0, c)] -> Num c
  | [(1, c)] -> if c = 1. then Var else Binop(Mul, Num c, Var)
  | (deg, coeff) :: rest ->
      (* 构造单项表达式：a*x^n *)
      let rec make_term deg coeff =
        match deg with
        | 0 -> Num coeff
        | 1 -> if coeff = 1. then Var else Binop(Mul, Num coeff, Var)
        | _ ->
            let var_pow = List.init (deg - 1) (fun _ -> Var) |> List.fold_left (fun acc _ -> Binop(Mul, acc, Var)) Var in
            if coeff = 1. then var_pow else Binop(Mul, Num coeff, var_pow)
      in
      (* 合并所有项为加法/减法链 *)
      List.fold_left (fun acc (d, c) ->
        let term = make_term d c in
        if c > 0. then Binop(Add, acc, term) else Binop(Sub, acc, make_term d (-.c))
      ) (make_term deg coeff) rest

(* 最终的simplify函数 *)
let simplify (e : expression) : expression =
  e
  |> expr_to_poly
  |> merge_like_terms
  |> poly_to_expr

(* 测试代码 *)
let print_simplified_expression expr_str =
  let simplified_expr = simplify (parse expr_str) in
  let stringified_expr = to_string_wo_paren simplified_expr in
  print_string stringified_expr;
  print_newline ();
;;

print_simplified_expression "3*x*x + 2*x - 5 + 4*x*x - 7*x";
print_simplified_expression "(x-1)*x*(x-5)";
print_simplified_expression "x - x";
print_simplified_expression "x + x + 0";
print_simplified_expression "0";

关键逻辑说明 #

1. 多项式表示：用(次数, 系数)的关联列表存储多项式，便于合并和运算。
2. 表达式转多项式：
   • 加法直接拼接两个多项式的项；减法将第二个多项式的系数取负后拼接。
   • 乘法通过双重循环展开，将每个项相乘后生成新项（次数相加，系数相乘）。
3. 合并同类项：遍历所有项，合并相同次数的系数，过滤系数为0的项，并按次数从高到低排序。
4. 多项式转表达式：将排序后的多项式项逐个转换为AST节点，用加法/减法连接，处理系数为1、次数为0/1等特殊简化情况。

测试结果 #

运行代码后输出与预期完全一致：

7.*x*x+-5.*x+-5.
1.*x*x*x+-6.*x*x+5.*x
0
2.*x
0

内容的提问来源于stack exchange，提问作者Zaring