I want to write a function where you enter a list of delimiters tuples, and a string, And the function should check if the string is balanced according to the tuples we input. And return a boolean value.
For example:
INPUT: balanceList [('[','}')] "[}"
OUTPUT: True
INPUT: balanceList [('{',')'] "{}"
OUTPUT: False
Here is my current code:
balanceList :: [(Char, Char)] -> String -> Bool
balanceList pairs string = balanced string emptyStack
where
balanced [] stack = isEmpty stack
balanced (c:string) stack
|c `elem1` (map fst pairs) = balanced string (push c stack)
|c `elem1` (map snd pairs) = popTest (pop stack)
where
popTest Nothing = False
popTest (Just (x,s)) = x == c && balanced string s
balanced (_:string) stack = balanced string stack
When I input balanceList [('[','}')] "[}"
I get False
instead of True
How can I solve this issue?
Thank you in advance
CodePudding user response:
With push c stack
, you are pushing the opening parenthesis on the stack, not the closing one. You thus check if the current character is the same as the opening when you check if it is closing.
A simpler approach is to push the expected closing parenthesis on the stack, and thus in that case pop the stack, so something like:
balanceList :: Eq a => [(a, a)] -> [a] -> Bool
balanceList pairs = go []
where go [] [] = True
go (c:ss) (c':cs)
| c == c' = go ss cs -- closing parenthesis
go s (c:cs)
| Just c' <- lookup c pairs = …
go _ _ = False
We here thus first check if both the stack and the string are empty, and then return True
. In case both the stack and string are not empty, we first check if the stack head c
and the first charcter of the string match, in which case we pop the stack and recurse on the tail of the string. If that fails, we check if the first charcter c
is an element of the pairs
, and we get the co-parenthesis c'
that we then need to push on the stack. I leave implementing this as an exercise.
CodePudding user response:
The problem is in this line:
|c `elem1` (map fst pairs) = balanced string (push c stack)
What are you pushing on the stack here?