Skip to content

Instantly share code, notes, and snippets.

@ivanfretes

ivanfretes/balanced_parenthesis.ts

Last active March 19, 2020 15:57
Show Gist options
  • Save ivanfretes/ca8f73cbee6d33137fdfeaeae500dc79 to your computer and use it in GitHub Desktop.
Save ivanfretes/ca8f73cbee6d33137fdfeaeae500dc79 to your computer and use it in GitHub Desktop.
Download ZIP
quanto-test-v2
Raw
balanced_parenthesis.ts
/**
* Verifica el primer y ultimo elemento
*
* O(1)
* @param simbols
*/
function verficarPrincipioFin(simbols : string ) : boolean{
const firstElement = simbols[0]
const lastElement = simbols[simbols.length - 1]
if (firstElement == ']' || firstElement == '}' || firstElement == ')')
return false;
if (lastElement == '[' || lastElement == '{' || lastElement == '(')
return false;
return true;
}
/**
* Genera un stack de simbolos y asigna la precedencia y la posicion del mismo
* En caso que no se den las condiciones retorna falso.
* Caso contrario genera un arreglo con dos elementos [stackOpen, stackClose],
* contiene una pila de simbolos de apertura y simbolos de clausura
*
* Mejor caso - O(1) : No se cumple una condicion al primer recorrido
* Peor caso - O(n) : Se cumplen todas las condiciones
*
* @param simbols - Cadena de simbolos
*
* @return {Array<any> | boolean}
*/
function generarStackDeSimbolor(simbols : string) : Array<any> | boolean{
let simbolsStack : Array<{simbol, importance, index}> = [];
let simbolsStackClose : Array<{simbol, importance, index}> = [];
let cantParentesisOpen : number = 0;
let cantParentesisClore : number = 0;
let cantLlaveOpen : number = 0;
let cantLLaveClore : number = 0;
let cantCorcheteOpen : number = 0;
let cantCorcheteClore : number = 0;
for (let i = 0; i < simbols.length; i++) {
const simbolsValue = simbols[i];
const simbolsNext = simbols[i + 1];
// Stack de simbolos abiertos
if (simbolsValue == '(' && (simbolsNext != ']' && simbolsNext != '}')){
cantParentesisOpen++;
simbolsStack.push({
simbol : simbolsValue,
importance : cantParentesisOpen ,
index : i
});
} else if (simbolsValue == '[' && (simbolsNext != ')' && simbolsNext != '}')) {
cantLlaveOpen++;
simbolsStack.push({
simbol : simbolsValue,
importance : cantLlaveOpen ,
index : i
});
} else if (simbolsValue == '{' && (simbolsNext != ')' && simbolsNext != ']')) {
cantCorcheteOpen++;
simbolsStack.push({
simbol : simbolsValue,
importance : cantCorcheteOpen,
index : i
});
} else if (simbolsValue == ')'){ // Stack de Simbolos Cerrados
cantParentesisClore++;
simbolsStackClose.push({
simbol : simbolsValue,
importance : cantParentesisClore ,
index : i
});
} else if (simbolsValue == ']'){
cantLLaveClore++;
simbolsStackClose.push({
simbol : simbolsValue,
importance : cantLLaveClore ,
index : i
});
} else if(simbolsValue == '}') {
cantCorcheteClore++;
simbolsStackClose.push({
simbol : simbolsValue,
importance : cantCorcheteClore,
index : i
});
} else {
return false;
}
}
return [ simbolsStack, simbolsStackClose ];
}
/**
* Verifica si Simbolos coinciden o no, en importancia(precedencia), elemento correspondiente
* y si el simbolo de apertura tiene una posicion inferior al simbolo de clausura.
* Si no hay problemas de coincidencia retorna true, caso contrario false
*
* Mejor caso - O(1) : No se cumple una condicion al primer recorrido
* Peor caso - O(n) : Se cumplen todas las condiciones
*
* @param simbolsStackOpen - Listado de simbolos de apertura
* @param simbolsStackClose - Listado de simbolos de clausura
*
* @return boolean
*/
function verificarSimbolosPorNivel(simbolsStackOpen : Array<any>, simbolsStackClose : Array<any>) : boolean {
if(simbolsStackOpen.length != simbolsStackClose.length) return false;
//console.log(simbolsStackOpen)
//console.log(simbolsStackClose)
simbolsStackOpen.sort(ordernarPorSimbolo)
simbolsStackClose.sort(ordernarPorSimbolo)
for (let i = 0; i < simbolsStackOpen.length; i++) {
let simbolsOpen : string = simbolsStackOpen[i].simbol;
let importanceOpen : number = simbolsStackOpen[i].importance;
let simbolsClose : string = simbolsStackClose[i].simbol;
let importanceClose : number = simbolsStackClose[i].importance;
let indexOpen : number = simbolsStackOpen[i].index;
let indexClose : number = simbolsStackClose[i].index;
if (importanceOpen != importanceClose ||
(simbolsOpen == '(' && simbolsClose != ')' && indexOpen > indexClose)||
(simbolsOpen == '[' && simbolsClose != ']' && indexOpen > indexClose) ||
(simbolsOpen == '{' && simbolsClose != '}' && indexOpen > indexClose ) ){
return false;
}
}
return true;
}
/**
* Ordena un listado en base a los simbolos almacenados
* @param a
* @param b
*
* O(n)
* Retorna si debe o no ordenarse
*/
function ordernarPorSimbolo(a : any, b : any) : number{
if (a.simbol < b.simbol) {
return -1
} else if(a.simbol > b.simbol){
return 1;
}
return 0;
}
/**
* Verifica si el listado de simbolos esta balanceado
*
*
* Peor cota para el caso - O(1 + 4N)
* Mejor Cota - O(1)
*
* @param simbols
* @return {boolean}
*/
function balancedParenthesis(simbols : string) : boolean{
let response : boolean = false;
let principioFin : boolean = verficarPrincipioFin(simbols)
if (principioFin){
let stacks : Array<any>|boolean = generarStackDeSimbolor(simbols)
if (stacks != false)
response = verificarSimbolosPorNivel(stacks[0], stacks[1])
} else
response = principioFin
return response;
}
console.log(balancedParenthesis("([{])"))
Raw
read_numbers.ts
/**
*
* @param x
*/
function readNumbers(x : number) : string {
let cadena : string = "11"
for (let i = 1; i < x; i++) {
let pivot : string = cadena[0]
let cantPivot : number = 0;
let cadenaTmp : string = '';
for (let j = 0; j < cadena.length; j++) {
if (cadena[j] == pivot){
cantPivot++
} else {
cadenaTmp += cantPivot + pivot
pivot = cadena[j]
cantPivot = 1;
}
if (j == (cadena.length - 1)){
cadenaTmp += cantPivot + pivot
}
}
cadena = cadenaTmp;
}
return cadena;
}
console.log(readNumbers(4));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment