更好地显示布尔公式

Question

我想实现一种在SML中显示命题公式的方法.到目前为止我找到的解决方案是这种类型的:

fun show (Atom a) = a
  | show (Neg p) = "(~ " ^ show p ^ ")"
  | show (Conj(p,q)) = "(" ^ show p ^ " & " ^ show q ^ ")"
  | show (Disj(p,q)) = "(" ^ show p ^ " | " ^ show q ^ ")";

这会产生不必要的括号:

((~p) & (q | r))

什么时候,我想拥有的是:

~ p & (q | r)

我看到,Haskell有一个功能(显示？),这很好地做到了这一点.有人可以帮助我一点点.我该怎么办呢？

Answer 1

如果要消除冗余括号,则需要传递一些优先级信息.例如,在Haskell中,showsPrec函数体现了这种模式; 它有类型

showsPrec :: Show a => Int -> a -> String -> String

其中第一个Int参数是当前打印上下文的优先级.额外的String参数是获得有效列表追加的技巧.我将演示如何为您的类型编写类似的函数,尽管在Haskell(因为我知道该语言最好)并且不使用额外的效率技巧.

我们的想法是首先构建一个没有顶级括号的字符串 - 但确实有消除子字符歧义所需的所有括号 - 然后仅在必要时添加括号.unbracketed下面的计算是第一步.那么唯一的问题是:我们什么时候应该在括号内加上括号？那么,答案就是当低优先级术语是高优先级运算符的参数时,事物应该被括起来.所以我们需要比较我们的直接"父"的优先级 - dCntxt在下面的代码中调用- 与我们当前渲染的术语的优先级 - dHere在下面的代码中调用.bracket下面的函数要么添加括号,要么根据此比较的结果单独保留字符串.

data Formula
    = Atom String
    | Neg  Formula
    | Conj Formula Formula
    | Disj Formula Formula

precedence :: Formula -> Int
precedence Atom{} = 4
precedence Neg {} = 3
precedence Conj{} = 2
precedence Disj{} = 1

displayPrec :: Int -> Formula -> String
displayPrec dCntxt f = bracket unbracketed where
    dHere       = precedence f
    recurse     = displayPrec dHere
    unbracketed = case f of
        Atom s   -> s
        Neg  p   -> "~ " ++ recurse p
        Conj p q -> recurse p ++ " & " ++ recurse q
        Disj p q -> recurse p ++ " | " ++ recurse q
    bracket
        | dCntxt > dHere = \s -> "(" ++ s ++ ")"
        | otherwise      = id

display :: Formula -> String
display = displayPrec 0

这是它在行动中的表现.

*Main> display (Neg (Conj (Disj (Conj (Atom "a") (Atom "b")) (Atom "c")) (Conj (Atom "d") (Atom "e"))))
"~ ((a & b | c) & d & e)"