Menu Close

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

   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
Medio

6 soluciones de “Expresiones equilibradas

  1. jaibengue
    equilibrada :: String -> Bool
    equilibrada = aux 0 0
      where aux m n (x:xs) | n > m     = False
                           | x == '('  = aux (m+1) n xs
                           | otherwise = aux m (n+1) xs
            aux m n _      | m == n    = True
                           | otherwise = False
    • pabhueacu

      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í:

      equilibrada :: String -> Bool
      equilibrada = aux 0 0
        where aux m n (x:xs) | n > m     = False
                             | x == '('  = aux (m+1) n xs
                             | otherwise = aux m (n+1) xs
              aux m n _ = m == n
  2. angruicam1
    equilibrada :: String -> Bool
    equilibrada cs | cs /= borra = equilibrada borra
                   | null cs     = True
                   | otherwise   = False
                       where borra = borrado "()" cs
     
    borrado :: String -> String -> String
    borrado _ []        = []
    borrado _ [a]       = [a]
    borrado xs (z:y:ys) | xs == [z,y] = borrado xs ys
                        | otherwise   = z:borrado xs (y:ys)
  3. María Ruiz
     
    import Data.List (foldl')
     
    equilibrada :: String -> Bool
    equilibrada xs = null $ foldl' f [] xs
      where f ('(':xs) ')' = xs
            f xs x         = x:xs
  4. pabhueacu
    equilibrada :: String -> Bool
    equilibrada xs = aux xs 0
      where aux [] y = y == 0
            aux (x:xs) y | y < 0 = False
                         | x == '(' = aux xs (y+1)
                         | otherwise  = aux xs (y-1)
  5. antgongar
    equilibrada :: String -> Bool
    equilibrada xs = null (aux [] xs)
      where aux ys       []       = ys
            aux ('(':ys) (')':xs) = aux ys     xs
            aux ys       (x:xs)   = aux (x:ys) xs

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.