Menu Close

Expresiones equilibradas

José A. Alonso,

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. Responder
    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
    • Responder
      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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.