JAVA: 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.

import java.util.*;

public class ParentesisBalanceados {

  public static boolean parentesisBalanceados(String cadena) { // Complejidad Tiempo O(n) | Espacio O(n)

    String apertura = "([{";

    String cierre = ")]}";

    Map<Character, Character> comparador = new HashMap<Character, Character>();

    comparador.put(')', '(');

    comparador.put(']', '[');

    comparador.put('}', '{');

    List<Character> pila = new ArrayList<Character>();

    for (int i = 0; i < cadena.length(); i++) {

      char caracter = cadena.charAt(i);

      if (apertura.indexOf(caracter) != -1) {

pila.add(caracter);

      } else if (cierre.indexOf(caracter) != -1) {

if (pila.size() == 0) {

  return false;

}

if (pila.get(pila.size() -1) == comparador.get(caracter)) { // Comparación

  pila.remove(pila.size() -1);

} else {

  return false;

}

      }

    }

    return pila.size() == 0;

  }


  public static void main(String[] args) {

    System.out.println(parentesisBalanceados("{[()]}"));

    System.out.println(parentesisBalanceados("{[(]}"));

  }

}

1. Una manera de resolver esto, es creando dos variables de cadena que contengan: la primera los caracteres de apertura, la segunda los caracteres de cierre.

2. Posteriormente se puede utilizar un HashMap para acceder a ellas.

3. 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.

4. 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