Beleza, o que é uma pilha?
Tá bem, sem enrolar muito vamos lá... A pilha é uma estrutura que a gente escuta falar direto, é basicamente uma lista (array) só que tem a condição de que a última coisa que entra é a primeira que sai.
No typescript temos acesso a dois métodos muito úteis já presentes nas listas, vamos primeiro criar uma lista vazia e partir pra entender melhor esses métodos:
// Criando uma lista vazia que possuirá números
const list: number[] = [];
/* Nós apenas acabamos de definir a variável `list`
* sendo do tipo `number[]`. o `number` é autoexplicativo,
* é um número! Já o `[]` diz que será um array do tipo que
* vem antes, ou seja, um array de números! */
Agora que temos nossa lista vazia, vamos entender melhor esses dois métodos.
push()
Esse aqui é bem simples, ele adiciona ao final da lista o que passarmos pra ele. Como a lista que criamos antes vai conter números somente, então devemos apenas adicionar números, por exemplo:
// Vamos adicionar os números 2, 4 e 6 na lista que criamos
list.push(2); // Adiciona 2
list.push(4); // Adiciona 4
list.push(6); // Adiciona 6
console.log(list); // [2, 4, 6]
Simples né? E como retorno, ela retorna o tamanho da lista após adicionar o elemento, por exemplo:
const newList: number[] = [];
const listLength = newList.push(2);
console.log(listLength); // 1
console.log(newList); // [2]
Como sempre recomendo que vocês sempre leiam a documentação para ver detalhes mais específicos do que vocês vão utilizar. Link para a documentação
pop()
Esse também é bem simples, ele remove o elemento do final da lista e retorna esse elemento que foi removido, bem assim:
// Nossa lista está com 3 elementos se lembra? adicionamos [2, 4, 6]
// Agora vamos remover o último elemento
let removed = list.pop();
console.log(removed); // 6
console.log(list); // [2, 4]
// Removendo o último elemento de novo
removed = list.pop();
console.log(removed); // 4
console.log(list); // [2]
Porém, tem um ponto de atenção que precisamos tomar cuidado! Ele só vai remover elemento da lista enquanto houver elemento né?
Caso a lista esteja vazia ele não irá remover nada e nos retornará undefined, tipo assim:
const emptyList = [];
const removed = emptyList.pop();
console.log(removed); // undefined
console.log(emptyList); // []
Ai é só um ponto pra tomar cuidado, mas é facilmente tratado.
Ok, push e pop, mas e a pilha?
Vamos lá, (só uma informação antes). Se lembra que no começo eu falei que na pilha "última coisa que entra é a primeira que sai"? Então, esse conceito na programação é chamado de FILO (First In Last Out) (Primeiro a entrar, último a sair)
Usando e entendendo pilhas
Vamos pensar em uma pilha de livros real em cima de uma mesa, lá temos 3 livros. Como somos desenvolvedores, vamos simular esses livros empilhados com uma lista (só que de cabeça para baixo).
const books = [
"Os três porquinhos", // Livro na base
"Chapeuzinho vermelho", // Livro no meio
"Alice no País das Maravilhas" // Livro no topo
];
Para você, é mais fácil pegar o livro que está em baixo de todos ou o que está em cima? Ao meu ver é mais fácil pegar o "Alice no país das maravilhas" do que levantar dois outros livros para poder pegar "Os três porquinhos", concorda?
Sendo assim, vamos pegar os livros do topo da pilha, para isso podemos usar o método pop que aprendemos.
let bookOnTop = books.pop();
console.log(bookOnTop); // "Alice no País das Maravilhas"
bookOnTop = books.pop();
console.log(bookOnTop); // "Chapeuzinho vermelho"
bookOnTop = books.pop();
console.log(bookOnTop); // "Os três porquinhos"
E agora nossa pilha está vazia, vamos adicionar um novo livro? Para isso também aprendemos o método push.
books.push("Crepúsculo");
console.log(books); // ["Crepúsculo"]
E é isso! Acabamos de entender como funciona uma pilha, só repassando tudo aqui:
- Sempre adicionamos no topo da pilha e removemos também do topo
- Para adicionar no topo utilizamos o método
push - Para remover do topo utilizamos o método
pop - Pilhas são do tipo FILO (First In Last Out) ou também podemos encontrar como LIFO (Last In First Out). Em ambos os casos é basicamente "O que entra por último, sai primeiro".
Isso é quase tudo! Leiam as documentações.
Agora praticando um pouquinho
O desafio de pilhas é o seguinte, você está trabalhando em um aplicativo de calculadora e o seu trabalho de hoje é criar uma função que cheque se os parênteses, colchetes e chaves de uma equação estão corretos, por exemplo:
Você receberá como entrada uma string como a string a seguir:
()[]{}
Podendo conter somente chaves, colchetes e parênteses, não terá nenhum outro caractere a não ser esses. A sua função deverá retornar verdadeiro caso a entrada seja válida ou falso caso não seja. Segue alguns exemplos de entrada abaixo:
1 - "()[]{}" // Entrada válida
2 - "([])" // Entrada válida
3 - "([{" // Entrada inválida, nenhum dos "(", "[" ou "{" abertos foram fechados
4 - "()]" // Entrada inválida, o "]" foi fechado sem ter um par abrindo
É esse o desafio, uma dica é se atentem aos casos extremos, por exemplo, e se a entrada for vazia?
⚠️ Solução
Ta bem, vamos lá para a solução. Primeiro tem algumas regras que nós vamos precisar pensar:
- Caso a entrada seja vazia, ela será válida pois não existe nada de errado nos parênteses, chaves ou colchetes da equação.
- Só podemos fechar um caractere se o último caractere aberto for do mesmo tipo, por exemplo:
(]não é válido, pois tentamos fechar com]só que o que estava aberto era(. - Precisamos ficar atentos aos casos onde só tiveram caracteres abertos, por exemplo
(((não é uma entrada válida.
Então bora, primeiro vamos pensar o seguinte toda vez que tiver um char (caractere) abrindo nós vamos precisar salvar ele e toda vez que tiver um char fechando, vamos olhar qual foi o tipo do último char aberto. Caso seja do mesmo tipo podemos continuar, caso não seja já não é mais válido, blz?
Então vamos lá, primeiro vamos passar por todos os caracteres da entrada:
const checkEquation = (input: string): boolean => {
// Vamos passar por todos os caracteres do input
for (const char of input) {
}
}
Vamos precisar criar um objeto para saber qual são os pares, por exemplo ( e ) são pares, e também precisamos checar quando que o caractere é abrindo e quando é fechando, para isso podemos só checar se o caractere é uma chave do nosso objeto de pares, se for então está abrindo.
const checkEquation = (input: string): boolean => {
// Objeto para os pares
const pairs = {
"(": ")",
"[": "]",
"{": "}"
};
// Vamos passar por todos os caracteres do input
for (const char of input) {
if (char in pairs) {
/* Caso {char} seja uma chave de {pairs} sabemos
que ele está abrindo */
} else {
// Caso não seja, ele está fechando
}
}
}
E agora é o seguinte, caso esteja abrindo nós precisamos salvar ele como o último char aberto, porém não podemos perder a referência dos anteriores também, é ai que entra a nossa pilha. Sempre que tiver abrindo vamos adicionar na pilha!
Caso precise ver o último char abrindo basta olhar o topo da pilha e o anterior fica lá até tirarmos o topo.
const checkEquation = (input: string): boolean => {
// Objeto para os pares
const pairs = {
"(": ")",
"[": "]",
"{": "}"
};
// Criamos um tipo para os caracteres abertos
type OpenChar = (keyof typeof pairs);
// Criamos nossa pilha de chars abertos
const queue = [];
// Vamos passar por todos os caracteres do input
for (const char of input) {
if (char in pairs) {
// Caso {char} seja uma chave de {pairs} sabemos
// que ele está abrindo.
// E adicionamos na pilha
queue.push(char);
} else {
// Caso não seja, ele está fechando
// Ai precisamos verificar se o último char aberto
// é do mesmo tipo.
// Primeiro antes de pegar o último aberto, vamos
// checar se a pilha está vazia, se estiver não é
// válido já que estaria tentando fechar sem ter
// aberto.
if (queue.length === 0) return false;
// Se chegou até aqui sabemos que a pilha não está
// vazia, então vamos pegar o topo.
const top = queue.pop() as OpenChar;
// E verificar se são do mesmo tipo, {top} vai ser
// um char abrindo então podemos pegar seu par pelo
// objeto {pairs} que criamos.
const pair = pairs[top];
// E verificamos se {char} e {pair} são iguais, se
// for é valido e podemos seguir, se não é inválido.
if (pair !== char) return false;
}
}
}
E agora precisamos checar dois pontos, primeiro caso a entrada seja vazia input.length === 0 e segundo caso a entrada seja só de char abertos, ai nossa pilha só teria char aberto, em outras palavras precisamos fechar todos os chars abertos para ser válido.
const checkEquation = (input: string): boolean => {
// Caso a entrada seja vazia
if (input.length === 0) return true;
// Objeto para os pares
const pairs = {
"(": ")",
"[": "]",
"{": "}"
};
// Criamos um tipo para os caracteres abertos
type OpenChar = (keyof typeof pairs);
// Criamos nossa pilha de chars abertos
const queue = [];
// Vamos passar por todos os caracteres do input
for (const char of input) {
if (char in pairs) {
// Caso {char} seja uma chave de {pairs} sabemos
// que ele está abrindo.
// E adicionamos na pilha
queue.push(char);
} else {
// Caso não seja, ele está fechando
// Ai precisamos verificar se o último char aberto
// é do mesmo tipo.
// Primeiro antes de pegar o último aberto, vamos
// checar se a pilha está vazia, se estiver não é
// válido já que estaria tentando fechar sem ter
// aberto.
if (queue.length === 0) return false;
// Se chegou até aqui sabemos que a pilha não está
// vazia, então vamos pegar o topo.
const top = queue.pop() as OpenChar;
// E verificar se são do mesmo tipo, {top} vai ser
// um char abrindo então podemos pegar seu par pelo
// objeto {pairs} que criamos.
const pair = pairs[top];
// E verificamos se {char} e {pair} são iguais, se
// for é valido e podemos seguir, se não é inválido.
if (pair !== char) return false;
}
}
// Precisamos garantir que todos os char abertos foram fechados
// para isso podemos só checar se a pilha ainda tem algum char.
return queue.length === 0;
}
E é isso, algum dos resultados:
console.log(checkEquation("")); // true
console.log(checkEquation("()[]{}")); // true
console.log(checkEquation("([{}])")); // true
console.log(checkEquation("([{")); // false
console.log(checkEquation("}])")); // false
Pode parecer assustador a princípio por ser muitas linhas de código mas é por causa dos comentários, segue abaixo a função sem comentários:
const checkEquation = (input: string): boolean => {
if (input.length === 0) return true;
const pairs = {
"(": ")",
"[": "]",
"{": "}"
};
type OpenChar = (keyof typeof pairs);
const queue = [];
for (const char of input) {
if (char in pairs) {
queue.push(char);
} else {
if (queue.length === 0) return false;
const top = queue.pop() as OpenChar;
const pair = pairs[top];
if (pair !== char) return false;
}
}
return queue.length === 0;
}
É isso, mas sempre comentem seus códigos viu!! Até a próxima estrutura de dados.
Top comments (0)