스택 문제풀이 - 괄호 짝 찾기

✏️ 문제

계산 수식이 주어졌을 때, 같은 짝의 괄호 위치를 찾는 프로그램을 제작하시오.
입력은 계산 수식으로 주어지며, 괄호의 짝 별 위치를 [시작, 끝]으로 찾아 2차원 배열 형태로 반환한다.
위치 시작 값은 0으로 시작하며, 하나라도 짝이 맞지 않을 경우 빈 배열을 반환한다.
입력값

(a+b)
(a*(b+c)+d+(e))
(a*(b+c)+d)+e)
(a*(b+c)+d)+(e*(f+g))

출력값

#1 [[0, 4]]
#2 [[3, 7], [0, 10]]
#3 []
#4 []
#5 [[3, 7], [0, 10], [15, 19], [12, 20]]

📝 풀이

// 기존에 없는 프로토타입 정의
if (!Array.prototype.peek) {
  Array.prototype.peek = function () {
    return this[this.length - 1];
  };
}

if (!Array.prototype.isEmpty) {
  Array.prototype.isEmpty = function () {
    return this.length == 0;
  };
}

function answer(str) {
  let result = [];

  let stack = [];
  for (let i = 0; i < str.length; i++) {
    if (str[i] == "(") {
      stack.push(i);
    } else if (str[i] == ")") {
      if (stack.isEmpty()) {
        return [];
      }

      result.push([stack.pop(), i]); // 2차원 배열
    }
  }

  if (!stack.isEmpty()) {
    return [];
  }

  return result;
}

1. str 문자를 순회하며 ( 가 있을 때 스택에 넣어주고 ) 를 만났을 때 result에 추가 한다.
2. 모든 연산이 끝난 후에도 (, )가 남아 있으면 빈 객체를 반환한다.
3. for문을 통해 문자열 하나하나에 접근한다.
4. 만약 ( 일 경우 stack에 인덱스([i])만 넣어준다.
   그리고 else if로 만약에 str[i]가 ) 일 경우 만약 stack이 비어 있는지 판단하고, 비어 있으면 ) 가 더 많다는 것을 판단할 수 있으니 빈 괄호를 반환하게 한다.
   이 경우가 아닐 경우 result에 push 한다.
5. 이렇게 작성하면 시작 괄호와 끝 괄호를 확인하고, 짝이 맞는지를 판단한다.
6. 그래도 만약에 스택에 (, ) 가 있으면, 짝이 맞지 않기 때문에 빈 괄호를 반환해주는 코드를 작성한다.