Balanced Brackets

관련 : stack 자료 구조

 

 

문제

문자열을 입력 받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴해야 한다.

 

 

Pseudocode

str[i]가 opener이면 stack 에 넣고

str[i]가 closer이면

1. stack에서 마지막 요소를 제거하고 이를 top이라고 한다.

2. top과 str[i]가 짝이 맞으면 true를 반환한다.

 

즉, stack에 쌓이는 것은 opener이고, str[i]가 closer일 때에는 이 closer가 stack에 가장 마지막에 넣은 요소와 짝이 맞는지 확인한다.

결과적으로 stack에 아무것도 남지 않게 되면 결과는 true이다.

 

 

코드 구현

const balancedBrackets = function(str) {

  let stack = [];
  let openers = {
    '(' : ')',
    '[' : ']',
    '{' : '}'
  }

  let closers = ')]}'

  for(let i = 0; i < str.length; i++){
    if(str[i] in openers){
      stack.push(str[i]);
    }else if(closers.includes(str[i])){ // closer가 나오면 opener와 짝이 맞는지 확인하기 위해
      let top = stack.pop(); // 가장 마지막에 넣은 opener를 꺼내고 top이라고 한다.
      let pair = openers[top] // 꺼낸 opener(top)에 해당하는 closer를 pair라고 할 때
      if(pair !== str[i]){ // 그 pair가 입력받은 closer(str[i])가 아니라면
        return false; // 바로 false를 반환하고 for문을 나온다.
      }
    }
  }
  return stack.length ===0; // 결과적으로 stack이 비었다면 true를 반환한다.
}