如何递归打印Standard ML中自定义的复杂s类型表达式？

嘿，这个问题我之前也碰到过——递归打印带运算符优先级的表达式，核心就是要处理好括号的添加，避免语义歧义。我来给你一步步拆解实现思路：

首先先回顾你定义的类型和infix运算符：

infix v; infix &;
datatype s = P | Q | S | ~ of s | v of s * s | & of s * s;

核心思路：优先级驱动的递归打印 #

直接递归打印每个构造器会有问题——比如~(P v Q)会被错误打印成~P v Q，这完全改变了原表达式的语义。解决办法是给每个运算符定义优先级，然后在递归打印时，根据当前上下文的优先级决定是否给子表达式添加括号：

• 一元运算符~：优先级最高（设为3）
• 二元运算符&：优先级次之（设为2）
• 二元运算符v：优先级最低（设为1）
• 原子节点（P/Q/S）：优先级最高（设为4，永远不需要括号）

我们需要一个辅助函数printS_prec，它接受当前表达式和当前上下文允许的最高优先级——如果子表达式的优先级低于这个值，就需要用括号包裹，避免歧义。主函数printS只需要调用这个辅助函数，初始上下文优先级设为0（最外层表达式不需要括号）。

完整实现代码 #

infix v; infix &;
datatype s = P | Q | S | ~ of s | v of s * s | & of s * s;

(* 辅助函数：带优先级的递归打印 *)
fun printS_prec (exp: s) (prec: int) : unit =
    case exp of
        P => print "P"
      | Q => print "Q"
      | S => print "S"
      | ~ e =>
          (print "~";
           (* ~的优先级是3，若当前上下文优先级高于3，子表达式需要加括号 *)
           if prec > 3 then print "(" else ();
           printS_prec e 3;
           if prec > 3 then print ")" else ())
      | e1 & e2 =>
          ( (* &的优先级是2，若当前上下文优先级高于2，整个表达式需要加括号 *)
            if prec > 2 then print "(" else ();
            (* 左操作数的上下文优先级设为2：如果左操作数是v（优先级1），会自动加括号 *)
            printS_prec e1 2;
            print " & ";
            (* 右操作数同样设为2，支持左结合的链式表达式（如P & Q & R） *)
            printS_prec e2 2;
            if prec > 2 then print ")" else ())
      | e1 v e2 =>
          ( (* v的优先级是1，若当前上下文优先级高于1，整个表达式需要加括号 *)
            if prec > 1 then print "(" else ();
            printS_prec e1 1;
            print " v ";
            printS_prec e2 1;
            if prec > 1 then print ")" else ())

(* 主函数：对外暴露的接口 *)
fun printS (exp: s) : unit =
    printS_prec exp 0;

测试例子 #

我们来验证你提到的复杂表达式P v ~ Q & P（对应SML表达式P v (~ Q & P)）：

printS (P v (~ Q & P));
(* 输出：P v ~ Q & P *)

再测试几个边界情况：

1. 嵌套否定：printS (~(P v Q)); → 输出~(P v Q)（正确添加括号，避免语义错误）
2. 链式运算符：printS (P & Q & R); → 输出P & Q & R（符合左结合语义）
3. 混合优先级：printS (~P & Q v ~S); → 输出~P & Q v ~S（自动处理优先级，无需多余括号）

关键细节解释 #

• 为什么用辅助函数？因为递归打印子表达式时，需要知道当前父运算符的优先级，从而决定是否加括号。
• 左结合处理：对于&和v这类左结合运算符，给右操作数传递相同的优先级，这样链式表达式不需要额外括号，符合SML的默认结合规则。
• 括号的添加逻辑：只有当子表达式的优先级低于当前上下文的优先级时，才添加括号，确保输出的表达式既简洁又语义准确。

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