Write a Prolog or Haskell program that recognizes if a string made of left and r

Question

Write a Prolog or Haskell program that recognizes if a string made of left and right parentheses is "well balanced" (as shown in the following examples):

Explanation / Answer

module Parens where import Data.Map (Map) import qualified Data.Map as Map matchingParens :: Map Char Char matchingParens = Map.fromList [ ('(', ')') , ('{', '}') , ('[', ']') ] isOpening :: Char -> Bool isOpening c = maybe False (const True) $ Map.lookup c matchingParens type Stack a = [a] balanced :: String -> Bool balanced = balanced' [] balanced' :: Stack Char -> String -> Bool balanced' [] "" = True balanced' _ "" = False balanced' [] (c:cs) = balanced' [c] cs balanced' (o:os) (c:cs) | isOpening c = balanced' (c:o:os) cs | otherwise = case Map.lookup o matchingParens of Nothing -> False Just closing -> if closing == c then balanced' os cs else False

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.