更好地显示布尔公式 [英] Better display of boolean formulas
问题描述
我想实现一个在SML中显示命题公式的方法。目前我发现的解决方案是这种类型的：
show（Neg p）=（〜^ show p ^）| show（Conj（p，q））=（^ show p ^&^ show q ^）
| show（Disj（p，q））=（^ show p ^|^ show q ^）;
这会产生不必要的大括号：
<$ p $ （$〜$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $'当我想要的是：
〜p& （q | r）
我看到，Haskell有一个函数（display？）， 。有人可以帮我一点点。我应该如何去解决这个问题？
解决方案如果你想消除多余的括号，你需要传递一些优先级信息。例如，在Haskell中， showsPrec 函数体现了这种模式;它有类型 showsPrec :: Show a => Int - > a - >字符串 - >字符串
其中第一个 Int 参数是当前打印上下文的优先顺序。多余的 String 参数是获得有效列表追加的一个技巧。我将演示如何为您的类型编写类似的函数，尽管在Haskell中承认（因为我知道这种语言最好），而不使用额外的效率技巧。
unbracketed 计算完成第一步。那么唯一的问题是：我们何时应该在我们的术语周围加上括号？那么，对此的答案是，当低优先级项是高优先级运算符的参数时，应加括号。因此，我们需要比较我们的直接父母的优先级 - 在下面的代码中称为 dCntxt - 与我们当前正在呈现的术语的优先级 - 称为在下面的代码中 dHere 。 数据公式
=原子字符串
| Neg Formula Formula
| Conj Formula Formula
| Disj Formula Formula
precedence ::公式 - > Int
优先级Atom {} = 4
优先级Neg {} = 3
优先级Conj {} = 2
优先级Disj {} = 1
displayPrec :: Int - >公式 - >字符串
displayPrec dCntxt f =括号未加括号的位置
dHere =优先级f
recurse = displayPrec dHere
unbracketed = case $ f
Atom s - > s
Neg p - > 〜++递归p
Conj p q - > recurse p ++&++递归q
Disj p q - >递归p ++|++递归q
括号
| dCntxt> dHere = \ s - > （++ s ++）
|否则= id
display :: Formula - >字符串
display = displayPrec 0
以下是它的外观。
*主要>显示（Neg（Conj（Disj（Conj（Atoma））（Atomb））（Atomc））（Conj（Atomd）（Atome））））
〜（（a& b | c）& d&e）
I want to implement a method for showing a propositional formula in SML. The solutions that I found so far was of this type:
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 ^ ")";
This produces unnecessary braces:
((~p) & (q | r))
when, what I'd like to have is:
~ p & (q | r)
I saw, that Haskell has a function (display?) which does this nicely. Can someone help me out a little bit. How should I go about this?
If you want to eliminate redundant parentheses, you will need to pass around some precedence information. For example, in Haskell, the showsPrec function embodies this pattern; it has type
showsPrec :: Show a => Int -> a -> String -> String
where the first Int argument is the precedence of the current printing context. The extra String argument is a trick to get efficient list appending. I'll demonstrate how to write a similar function for your type, though admittedly in Haskell (since I know that language best) and without using the extra efficiency trick.
The idea is to first build a string that has no top-level parentheses -- but does have all the parentheses needed to disambiguate subterms -- then add parentheses only if necessary. The unbracketed computation below does the first step. Then the only question is: when should we put parentheses around our term? Well, the answer to that is that things should be parenthesized when a low-precedence term is an argument to a high-precedence operator. So we need to compare the precedence of our immediate "parent" -- called dCntxt in the code below -- to the precedence of the term we're currently rendering -- called dHere in the code below. The bracket function below either adds parentheses or leaves the string alone based on the result of this comparison.
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
Here's how it looks in action.
*Main> display (Neg (Conj (Disj (Conj (Atom "a") (Atom "b")) (Atom "c")) (Conj (Atom "d") (Atom "e"))))
"~ ((a & b | c) & d & e)"
这篇关于更好地显示布尔公式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
