0

这是树的定义：data Tree = Leaf Char | Node (Char, Tree, Tree)

我想以treeToInfix如下形式编写一个函数：

treeToInfix :: Tree -> String

这里有些例子：

treeToInfix (Node ('*', (Node ('+', (Leaf 'a'), (Leaf 'b'))), (Leaf 'c'))) 
-- =>  "(a+b)*c"

treeToInfix (Node ('-', (Node ('+', (Leaf 'a') ,(Leaf 'b'))), (Leaf 'c')))
-- =>  "a+b-c"

treeToInfix (Node ('-', (Leaf 'c'), (Node ('+', (Leaf 'a') ,(Leaf 'b')))))
-- =>  "c-(a+b)"

treeToInfix (Node ('*', (Node ('/', (Leaf 'a'), (Leaf 'b'))), (Node ('/', (Leaf 'c'), (Leaf 'd'))))) 
-- =>  "a/b*c/d"

treeToInfix (Node ('+', (Node ('-', (Leaf 'a'), (Node ('*', (Leaf 'b'), (Leaf 'c'))))), (Node ('/', (Leaf 'd'), (Leaf 'e'))))) 
-- =>  "a-b*c+d/e"

我需要有关此程序算法的帮助。

4

2 回答 2

1

鉴于这看起来像你的作业，我只是给出一个大致的想法。每个运算符都有优先级（可能还有关联性）。这可以简单地表示为一个数字。因此，这个想法是将上下文的关联性作为附加参数打印出来。所以你的函数可能看起来像这样：

treeToInfix :: Tree -> String
treeToInfix tr = treeAux 0 tr


treeAux :: Int -> Tree -> String
treeAux prec (Node ("+",left,right)) = 
  -- TODO:
  --   * let's say precedence of '+' is 5
  --   * generate strings for children (with prec = 5)
  --   * put "+" in between
  --   * if prec > 5, put parantheses around the result
-- Similar for other cases

您甚至可以通过改变传递给递归调用的优先级来实现关联性。

于 2011-03-13T21:16:18.217 回答
0

好吧，如果您考虑一下，操作的每个阶段都需要：

  1. 为左操作数生成字符串
  2. 为运算符生成字符串
  3. 为右操作数生成字符串
  4. 以正确的顺序将它们粘在一起

请注意，为左右操作数生成字符串只是树对字符串函数的另一个应用，因此您可以递归地编写代码。您没有递归定义的基本情况将是如何显示叶子。

如果您想确保仅在运算符优先级需要时插入括号，它会稍微复杂一些，但我假设您不介意在函数结果中有一些额外的，严格来说是不必要的括号。

这足够帮助吗？我尽量避免只给你代码，以防这是一个家庭作业问题。我还假设您了解递归，因为它是 Haskell 中的一项关键技能。如果你不了解递归，请告诉我，我会写更多。

于 2011-03-13T21:11:59.577 回答