Expresiones equilibradas

José A. Alonso

30-11-2017

Una cadena de paréntesis abiertos y cerrados está equilibrada si a cada paréntesis abierto le corresponde uno cerrado y los restantes están equilibrados. Por ejemplo, "(()())" está equilibrada, pero "())(()" no lo está.

Definir la función

equilibrada :: String -> Bool

tal que (equilibrada cs) se verifica si la cadena cs está equilibrada. Por ejemplo,

equilibrada "(()())"          ==  True
equilibrada "())(()"          ==  False
equilibrada "()"              ==  True
equilibrada ")(()))"          ==  False
equilibrada "("               ==  False
equilibrada "(())((()())())"  == True

Soluciones

import Data.List (foldl')
import Test.Hspec

-- 1ª definición
equilibrada :: String -> Bool
equilibrada = aux 0 where
  aux 0 []       = True
  aux n ('(':cs) = aux (n + 1) cs
  aux n (')':cs) = n > 0 && aux (n - 1) cs
  aux _ _        = False

-- 2ª definición
equilibrada2 :: String -> Bool
equilibrada2 = aux 0 where
  aux n []       = n == 0
  aux n ('(':ps) = aux (n+1) ps
  aux n (')':ps) = n > 0 && aux (n-1) ps

-- 3ª definición
equilibrada3 :: String -> Bool
equilibrada3 xs = null $ foldl' op [] xs where
  op ('(':xs) ')' = xs
  op xs x = x:xs