Kata #2 - Balanced Parentheses

What does the fox say? Ring-ding-ding-ding-dingeringeding!

El Kata balance de paréntesis es una pregunta muy común en las entrevistas para ver el potencial de un desarrollador y dice así: dada una cadena de apertura y cierre de paréntesis, verificar si es equilibrada. Tenemos 4 tipos de paréntesis: paréntesis: (), corchetes: [], llaves: {} y tags: <>. La cadena no contiene ningún otro caractér. Los paréntesis balanceados requieren estar cerrados de una manera correcta. Por ejemplo ‘([])’ es equilibrado, pero ‘([)]’ no lo es.

Esta es otra pregunta sobre estructuras, y una muy sencilla si pensamos con detenimiento las reglas. Nuestro string debe ser par, ya que para tener un balance correcto, se necesita un caractér de apertura y uno de cierre. Si escaneamos de izquierda a derecha y guardamos todos aquellos paréntesis de apertura en un stack, al encontrarnos con un paréntesis de cierre tendríamos que verificar si el último del elemento guardado en el stack es uno de apertura de su misma clase. Esto quiere decir que si nuestro stack está vacio, significa que está balanceado, de caso contrario no lo estaría por que tendremos paréntesis abiertos que no fueron cerrados.

Para resolver éste problema vamos a utilizar Javascript -_en otros katas usaré Ruby u otro lenguaje, pero actualmente estoy emocionado con JS_- y convertiremos conceptos muy sencillos a cosas de ES2015 -_ES6 pa’ los cuates_-.

let tags = {
  "(" : ")",
  "<" : ">",
  "{" : "}",
  "[" : "]"
};

function isOpenTag(elem){
  for(let key in tags){
    if (elem == key){
      return true;
    }
  }
  
  return false;
}

function isCloseTag(elem){  
  for(let key in tags){
    if (elem == tags[key]){
      return tags[key];
    }
  }
  
  return false;
}

En ES5 no tenemos Hash Tables, por lo que para emularlas creamos un objecto con los paréntesis de apertura como keys y los de cierre como values. Creamos también dos funciones isOpenTag y isCloseTag. El primero buscará si el elemento es un paréntesis de apertura buscando con un for…in, retornando un boolean como respuesta. El segundo buscará si el elemento es un paréntesis de cierre, utilizando la misma lógica que el anterior pero con la diferencia de que éste nos retornará el paréntesis de apertura. Esto nos servirá para en un futuro comparar si el paréntesis del “stack” concuerda, es decir, que son del mismo tipo y efectivamente están balanceados.

Haremos mas divertidas las cosas y en lugar de usar el código anterior, vamos a simplificar la vida y usaremos Map de ES6 -_no confundir con la función map_-, que es un Hash Map para javascript - \(;゚∇゚)/ wiiii - y replicaremos la función isCloseTag en una función key dentro de Map. Oh claro, y como somos niños grandes vamos a crear una función last en nuestros Arrays para que nos retornen el último valor -_podríamos hacer un simple pop, pero nos quitaría mucha diversión… por eso la palabra “podríamos”._-

Map.prototype.key = function(value){
  for(var [key, val] of this.entries()) {
    if(value === val) return key;
  }
  return false;
};

Array.prototype.last = function(){
  return this[this.length-1];
};

function isValid(str){
  str = str.split("");
  
  let tags = new Map (
    [
      ["(" , ")"], 
      ["<" , ">"],
      ["{" , "}"],
      ["[" , "]"]
    ]
  );

  let openTags = [];
}

console.log(isValid("({}[]())<>")); // true

Bien, ahora solo falta lo mas sencillo, y es recorrer el string -_mismo que ya hemos transformado en un array gracias a la función split- y realizar la comparación. Los objectos Map tienen un método has para verificar si existe un _key en la colección, así que esa es la función que usaremos para verificar si el elemento actual de nuestro Array existe en la colección, allí es donde la magia radica en nuestro código. De caso contrario usaremos la función que hemos creado con el nombre de key, significando que nos hemos topado con un paréntesis de cierre y vamos a ver si su apertura es el mismo que el último del stack, al cual hemos llamado openTags. Nuestro código quedaría así:

/**
 * Returns the key of an occurrence of a given value. If the value is not found, returns false.
 * @this {Map}
 * @param {Object} value - The value to search.
 * @returns {Object | boolean}
 */
Map.prototype.key = function(value){
  for(var [key, val] of this.entries()) {
    if(value === val) return key;
  }
  return false;
};

/**
 * Returns the last element of an Array
 * @this {Array}
 * @returns {Object | boolean}
 */
Array.prototype.last = function(){
  return this[this.length-1];
};

function isValid(str){
  str = str.split("");
  
  let tags = new Map (
    [
      ["(" , ")"], 
      ["<" , ">"],
      ["{" , "}"],
      ["[" , "]"]
    ]
  );

  let openTags = [];

  for(let i=0; i < str.length; i++){
    let key;
    if(tags.has(str[i])){
      openTags.push(i);
    }else if( (key = tags.key(str[i])) ){
      if(key == str[openTags.last()]){
        openTags.pop();
      }else{
        return false;
      }
    }
  }

  if(openTags.length === 0){
    return true;
  }else{
    return false;
  }
}

console.log(isValid("({}[]())<>"));

JS Bin on jsbin.com

Muy sencillo, ¿no lo creen?. Claro, podemos mejorar el código con mas condiciones como por ejemplo de que nuestra cadena de texto sea par, no sea nula, vacia u otro tipo de cosa, pero recuerden que eso es sencillo de establecer y nos enfocamos mas en el algoritmo, y los katas -_así como las entrevistas_- se enfocan mucho en que nos darán datos que cumplan ciertas condiciones sin que tengamos que preocuparnos por otro tipo de validaciones.

Espero que les haya gustado éste kata, lo pude haber resuelto con Ruby ya que el lenguaje tiene muchas utilidades, pero quise aprovechar el poder que nos está entregando ES2015. Recuerden que hay una sección de comentarios abajo donde podemos interactuar con dudas o aportaciones para mejorar.

Nos leemos!!!