GO: Paréntesis Balanceados

  Escribe una función que valide si un número dado de paréntesis, corchetes y llaves se encuentran correctamente abiertos y cerrados.



package main

import "fmt"

var apertura = map[rune]bool{

  '(': true,

  '[': true,

  '{': true,

}

var cierre = map[rune]bool{

  ')': true,

  ']': true,

  '}': true,

}

var comparador = map[rune]rune{

  ')': '(',

  ']': '[',

  '}': '{',

}


func ParentesisBalanceados(cadena string) bool { // Complejidad Tiempo O(n) | Espacio O(n)

  pila := []rune{}

  for _, caracter := range cadena {

    if _, encontrado := apertura[caracter]; encontrado {

      pila = append(pila, caracter)

      continue

    }

    if _, encontrado := cierre[caracter]; encontrado {

      if len(pila) == 0 {

return false

      }

      if pila[len(pila)-1] == comparador[caracter] { // Comparación

pila = pila[0 : len(pila)-1]

      } else {

return false

      }

    }

  }

  return len(pila) == 0

}


func main() {

  fmt.Println(ParentesisBalanceados("{[()]}"))

  fmt.Println(ParentesisBalanceados("{[(]}"))

}

1. Una manera de resolver esto, es creando tres mapas que contengan: el primero los caracteres de apertura, el segundo los caracteres de cierre y un tercero el comparador de caracteres.

2. Finalmente se almacena una pila en un arreglo (o lista), y con una comparación por posición, se va liberando de memoria aquel elemento que ha encontrado a su pareja a continuación.

3. Considerar que el orden de apertura y cierre es importante. Ya que pueden estar anidados, pero por nivel, lo que abre, tiene que cerrar, para que la función retorne True. Es False si no se encuentra el cierre en el lugar correcto.

0 remarks:

Publicar un comentario