Haskell - convert postfix expression to binary tree

Question

I am trying to convert postfix expression to binary tree. My function takes as argument a list of tokens (strings).

Everytime I give the function any input, debugger writes a message: Non-exhaustive patterns in function "add".

My idea was: read a token after token and determine, if it is an operator or an operand. If it is operand, don't save any node to the tree and store the number to the stack. Otherwise I create a node with an operator, pop symbols from stack, set them as children of new node and push the operator to stack.

If the list of strings is empty, functions print the binary tree.

Would someone explain to me, why the function gives non-exhaustive patterns error and how can I fix the function?

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)) []

What about add Empty [] x? Or add (Leaf x) token []? Are you sure that you captured all patterns that can happen in add itself? — Zeta
I will try to write a code for patterns: add (Leaf x) token [] — Mafi
I was thinking about your question and I am not sure, if there is a situation in the algorithm, when the stack is empty, current node is a leaf and string is non-empty. — Mafi

Igor Drozdov Igor Drozdov · Accepted Answer · 2017-08-21T17:40:14

I've managed to reproduce the error by simple example:

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

The program successfully adds Leaf "10" to the stack, but can't add Leaf "1" to the stack, because the add is called with the following args:

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

But it doesn't match any pattern, because add Empty (x:xs) (a:b:bs) expects the third argument to have two Tree elements and a list. Therefore, a pattern that matches third argument as a list with one element is needed. For example, adding:

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

fixes the error and prints the following:

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

Hope it'll help you to continue with the task, unless you've already solved it :)

Haskell - convert postfix expression to binary tree

1 Answers