Expresiones equilibradas
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
1 |
equilibrada :: String -> Bool |
tal que (equilibrada cs) se verifica si la cadena cs está equilibrada. Por ejemplo,
1 2 3 4 5 6 |
equilibrada "(()())" == True equilibrada "())(()" == False equilibrada "()" == True equilibrada ")(()))" == False equilibrada "(" == False equilibrada "(())((()())())" == True |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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 |
En el auxiliar sería posible eliminar las últimas dos guardas, ya que si m == n te devolverá directamente True y si no lo es ya te dará el False sin necesidad de guardas.
La definición quedaría tal que así: