자바스크립트 스택 알고리즘 문제 풀이, 괄호 계산

문제 설명

4개의 기호 (, ), [, ] 를 이용해서 만들어지는 괄호열로, 아래 규칙으로 계산하는 프로그램을 작성.

1. "()"인 괄호 열 값은  2

2. "[]"인 괄호 열 값은 3

3. "( )" 안에 들어가 있는 값은 *2

4. "[ ]" 안에 들어가 있는 값은 *3

5. 괄호가 여러개 있으면 괄호 + 괄호

 

ex) ()[[]]는 2 + 3 * 3 = 11이 나온다. ([])의 값은 2 * 3으로 6이다.

조건, 괄호의 쌍이 맞지 않거나 기호 순서가 비정상적인 경우에는 0을 반환한다.

 

입력은 4개의 기호로만 이루어진 괄호가 문자열 형태로 주어진다.

- 이 문제를 stack으로 풀려고 했을 때 계산하는게 힘들었다.

()그냥 괄호면 2이지만 ()안에 다른게 있으면 *를 해줘야한다.

 

 

 

코드 풀이

function answer(str) {
  let result = 0;
  let stack = [];
  let temp = 1;
  for (let i = 0; i < str.length; i++) {
    switch (str[i]) {
      case "(":
        temp *= 2;
        stack.push(str[i]);
        break;
      case "[":
        temp *= 3;
        stack.push(str[i]);
        break;
      case ")":
        if (stack.length === 0 || stack[stack.length - 1] != "(") {
          return 0;
        }
        if (str[i - 1] == "(") {
          result += temp;
        }
        stack.pop();
        temp /= 2;
        break;
      case "]":
        if (stack.length === 0 || stack[stack.length - 1] != "[") {
          return 0;
        }
        if (str[i - 1] == "[") {
          result += temp;
        }
        stack.pop();
        temp /= 3;
        break;
    }
  }

  if (stack.length !== 0) {
    return 0;
  }
  return result;
}

 

- 문자열을 하나씩 받는다. if문이 아닌 switch문을 통해서 case별로 나누었다.

- 변수 temp를 통해서 값들을 곱하고 더하면서 result에 값을 저장하는 방식이다.

- "(" 이면 temp에 2를 곱한다. 그리고 stack에 push를 한다.

- "[" 이면 temp에 3을 곱한다. 그리고 stack에 push를 한다.

- ")" 이면 if를 통해서 stack의 길이가 0이거나, 현재 stack의 마자막에 있는 요소가 "("열린 괄호가 아닌지 확인한다.

* 만약 stack에 아무것도 없으면 열린 "("가 없기 때문에 0을 return한다.

* 만약 현재 stack에서 마지막 요소가  "("열린 괄호가 아니라면 0을 return 한다.

** 이 두개를 확인하는 이유는 바로 전에 있는 괄호가 "("열린 괄호라면 제대로된 괄호이기 때문이다.

* 그리고 이전 문자가"("열린 괄호였다면 result에 temp값을 저장한다.

* 그리고 stack에서 pop()으로 처리한 괄호를 빼주고 temp는 /2를 해준다.

 

- "]" 이것도 똑같이 확인 후 다른점은 temp에 /3을 나눠준다.

 

- 마지막으로 stack의 길이가 0인지 확인하고 0이 아니면 return 0을 한다.

 

ex ) (()[[]])

i = 0;

str[i] = (

case "("

temp = 1 * 2 = 2

result = 4

stack = (

break;

 

i = 1;

str[i] = (

case "("

temp = 2 * 2 = 4

result = 0

stack = ((

break;

 

i = 2;

str[i] = )

case ")"

if stack.length는 0이 아니다, 현재 스택은 (이다. pass

if str[i - 1] 이전 str이 (였으므로 조건 만족 result값에 temp 저장

temp = 4, temp값을 result에 저장 하고 / 2

temp = 2

result = 4

stack = (( .pop() = (

break;

 

i = 3;

str[i] = [

case "["

temp = 2 * 3 = 6

result = 4

stack = ([

break;

 

i = 4;

str[i] = [

case "["

temp = 6 * 3 = 18

result = 4

stack = ([[

break;

 

i = 5;

str[i] = ]

case "]"

if stack.length는 0이 아니다, 현재 스택의 끝은 [이다. pass

if str[i -1] 이전 문자가 [ 이므로 조건 만족

temp = 18, temp값을 result에 저장 하고 / 3

temp = 6

result = 22

stack = ([[ .pop() = ([

break;

 

i = 6;

str[i] = ]

case "]"

if stack.length는 0이 아니다, 현재 스택의 끝은 [이다. pass

if str[i -1] 이전 문자가 ] 이므로 pass

temp = 6, temp / 3

temp = 2

result = 22

stack = ([ .pop() = (

break;

 

i = 7;

str[i] = )

case ")"

if stack.length는 0이 아니다, 현재 스택의 끝은 (이다. pass

temp = 2, temp / 2

temp = 1

result = 22

stack = ( .pop() = 

break;

 

for문을 다 돌고 만약 stack의 길이가 0이 아니면 return 0