Haskell

Question

我正在尝试将后缀表达式转换为二叉树。我的函数将标记（字符串）列表作为参数。

每次我为函数提供任何输入时，调试器都会写入一条消息：函数中的非详尽模式 "add"。

我的想法是：一个接一个地读取一个标记并确定它是一个运算符还是一个操作数。如果是操作数，则不将任何节点保存到树中并将数字存储到堆栈中。否则我创建一个带有运算符的节点，从堆栈中弹出符号，将它们设置为新节点的子节点并将运算符压入堆栈。

如果字符串列表为空，函数打印二叉树。

有人可以向我解释一下为什么该函数会出现非详尽模式错误吗？我该如何修复该函数？

data Tree = Leaf String | Empty | Node Tree String Tree deriving (Show)

add :: Tree -> [String] -> [Tree] -> Tree
add (Node l v p) [] stack = (Node l v p)
add Empty (x:xs) []
        | x `elem` ["*","-","+"] = add (Leaf x) xs [Leaf x]
        | otherwise = add Empty xs [Leaf x]
add Empty (x:xs) (a:b:bs)
        | x `elem` ["*","-","+"] = add (Node b x a) xs (Leaf x:a:b:bs)
        | otherwise = add Empty xs (Leaf x:a:b:bs)
add (Leaf x) token (a:b:bs)
        | x `elem` ["*","-","+"] = add (Node b x a) token (Leaf x:bs)
        | otherwise = Leaf x
add (Node l v p) (x:xs) (a:b:bs)
        | x `elem` ["*","-","+"] = add (Node b x a) xs (Leaf x:bs)
        | otherwise = add (Node l v p) xs (Leaf x:a:b:bs) 

parse :: String -> Tree
parse input = add Empty (words (toPostfix input)) []

Answer 1

我已经通过简单的例子重现了这个错误：

add Empty ["10", "1", "+"] []

程序成功将Leaf "10"入栈，但无法将Leaf "1"入栈，因为add是用以下args调用的：

add Empty ["1", "+"] [Leaf "10"]

但它不匹配任何模式，因为 add Empty (x:xs) (a:b:bs) 期望第三个参数有两个 Tree 元素和一个列表。因此，需要一种将第三个参数匹配为具有一个元素的列表的模式。例如，添加：

add Empty (x:xs) [a] = add Empty xs (Leaf x:[a])

修复错误并打印以下内容：

Node (Leaf "10") "+" (Leaf "1")

希望它能帮助你继续完成任务，除非你已经解决了它:)

Haskell - 将后缀表达式转换为二叉树

Haskell - convert postfix expression to binary tree

recursion

binary-tree

postfix-notation