隨着算術表達式的解析樹如何生成在Haskell

這裏中綴表達式的結果是樹的定義：data Tree = Leaf Char | Node (Char, Tree, Tree)隨着算術表達式的解析樹如何生成在Haskell

我想要的形式寫一個函數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"

我需要這個程序的算法幫助。

來源

2011-03-13 fwegmk

可能是作業問題？ –

好吧，如果你想想看，在操作的每個階段需要爲：

產生了左操作數字符串
生成字符串操作
生成正確的操作數
串以正確的順序將它們粘合在一起

請注意，爲左側和鑽機生成字符串ht操作數僅僅是你的樹的另一個字符串函數應用程序，所以你可以遞歸地編寫它。你的基本情況，你沒有遞歸定義，將會是如何顯示一個Leaf。

如果你想要確保括號只在運算符優先級需要時插入，它會變得稍微複雜一點，但我假設你不介意在函數結果中有一些額外的，嚴格來說不必要的括號。

這有足夠的幫助嗎？我試圖避免只是給你的代碼，以防萬一它是一個家庭作業問題。我還假設你理解遞歸，因爲它是Haskell的關鍵技能。如果你不明白遞歸，那麼讓我知道，我會寫更多。

來源

2011-03-13 21:11:59 chrisdb

如果你想刪除不必要的括號，請參閱nominolo的答案。我建議你從簡單的案例開始編寫代碼，然後在對簡單案例感到滿意後再添加額外的優先級信息。 – chrisdb

鑑於這看起來像作業你，我只是給一個大致的想法。每個操作員都有優先權（可能還有關聯性）。這可以簡單地表示爲一個數字。那麼，這個想法就是將上下文的關聯性作爲附加參數來打印。所以，你的功能可能是這樣的：

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-13 21:16:18 nominolo

隨着算術表達式的解析樹如何生成在Haskell

回答

相關問題