打印表达式时最小化括号

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)

是否有一个 "easy" 可以在展示实例中考虑到这一点？我想我可以通过考虑所有情况来做到这一点，但这将是功能的爆炸式增长。是否有某种算法或已知方法来处理此问题？

希望大神指点！

谢谢。

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，优先级为 8，以给出右关联方式的例子）：

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.

中区分它们

实际上，你可以偷看下一层并重新关联：

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 (Add e2 e3)) = showsPrec prec (Add (Add e1 e2) e3)
  showsPrec prec (Add e1 e2) = showParen (prec >= 7) $ showsPrec 6 e1 . showString " + " . showsPrec 7 e2
  showsPrec prec (Mul e1 (Mul e2 e3)) = showsPrec prec (Mul (Mul e1 e2) e3)
  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

我认为这是完美的。您所有的测试用例现在都通过了。

打印表达式时最小化括号

Minimize parenthesis when printing expression

recursion

haskell

expression

arithmetic-expressions