Check Balance Delimiters Function Haskell-CodePudding

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 Falseinstead 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?