打印表达式时最小化括号

Question

我有一个希望能够打印的简单算术表达式数据结构。为了简单起见，在此我以3个二进制运算（加法，乘法和除法）为例。定义看起来像这样：

module ExprPrint where

import Text.Printf

data Expr = Lit Int
          | Add Expr Expr
          | Mul Expr Expr
          | Div Expr Expr

instance Show Expr where
  show (Lit x) = show x
  show (Add e1 e2) = printf "(%s) + (%s)" (show e1) (show e2)
  show (Mul e1 e2) = printf "(%s) * (%s)" (show e1) (show e2)
  show (Div e1 e2) = printf "(%s) / (%s)" (show e1) (show e2)

我的目标是在删除所有多余的括号的同时打印数据结构。当然，我在上面实现的天真显示功能包括太多这样的功能。因此，我想做的是使Show实例具有优先级（Div和Mul高于Add）和关联性（Add和Mul是关联的，而Div是左关联的）操作的数量。

以下是一些示例：

one = Lit 1

-- Shows "((1) + (1)) + (1)" but should be 1 + 1 + 1
addAssoc = show $ Add (Add one one) one
-- Shows "((1) * (1)) * (1)" but should be 1 * 1 * 1
mulAssoc = show $ Mul (Mul one one) one
-- Shows "((1) / (1)) / (1)" but should be 1 / 1 / 1
divAssoc = show $ Div (Div one one) one
-- Shows "(1) / ((1) / (1)) but should be 1 / (1 / 1)
divAssoc2 = show $ Div one (Div one one)

-- Show "((1) * (1)) + (1)" but should 1 * 1 + 1
addPrec = show $ Add (Mul one one) one
-- Show "(1) + ((1) * (1))" but should show 1 + (1 * 1)
addPrec2 = show $ Add one (Mul one one)

在显示实例中是否有“简便”的考虑因素？我认为我可以通过考虑所有情况来做到这一点，但这将是功能的爆炸式增长。是否有某种算法或已知方法可以处理此问题？

我希望有人有指点！

谢谢。

Answer 1

根据show的实例不足以避免使用多余的括号，因为它没有任何有关优先级的信息。您需要改为使用showsPrec来编写实例，如下所示：

module ExprPrint where

import Text.Show

data Expr = Lit Int
          | Add Expr Expr
          | Mul Expr Expr
          | Div Expr Expr

instance Show Expr where
  showsPrec prec (Lit x) = showsPrec prec x
  showsPrec prec (Add e1 e2) = showParen (prec >= 7) $ showsPrec 7 e1 . showString " + " . showsPrec 7 e2
  showsPrec prec (Mul e1 e2) = showParen (prec >= 8) $ showsPrec 8 e1 . showString " * " . showsPrec 8 e2
  showsPrec prec (Div e1 e2) = showParen (prec >= 8) $ showsPrec 8 e1 . showString " / " . showsPrec 8 e2

我为您的优先级选择了6和7，因为那是Haskell为其自己的+，*和div运算符使用的，但是很明显，您将如何选择其他运算符。

至于关联性，通常没有完美的方法，但是您可以根据情况进行一些优先级调整来伪造它，因为数学中没有任何运算符具有相同的优先级且具有不同的关联性。这是如何执行此操作的示例（我添加了Exp来给出执行此操作的右关联方法的示例）：

module ExprPrint where

import Text.Show

data Expr = Lit Int
          | Add Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | Exp Expr Expr

instance Show Expr where
  showsPrec prec (Lit x) = showsPrec prec x
  showsPrec prec (Add e1 e2) = showParen (prec >= 7) $ showsPrec 6 e1 . showString " + " . showsPrec 7 e2
  showsPrec prec (Mul e1 e2) = showParen (prec >= 8) $ showsPrec 7 e1 . showString " * " . showsPrec 8 e2
  showsPrec prec (Div e1 e2) = showParen (prec >= 8) $ showsPrec 7 e1 . showString " / " . showsPrec 8 e2
  showsPrec prec (Exp e1 e2) = showParen (prec >= 9) $ showsPrec 9 e1 . showString " ^ " . showsPrec 8 e2

这仍然不完美，因为它仍然不知道Add或Mul的关联属性，因此Mul one (Mul one one)将显示为1 * (1 * 1)而不是1 * 1 * 1，但我认为没有任何关联解决此问题的可能方法，因为除法不共享该属性，但是由于它的优先级与乘法相同，因此您无法在showsPrec中将它们区分开。