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 に答える