알고리즘 : 후위식 연산 문제 풀이 (인프런 강좌)

문제

 

인프런 JS 알고리즘 강좌 문제를 한번 풀이해보겠습니다.

 

강좌 바로가기

 

 

문제 해석

 

해당 문제는 스택을 이용한 풀이 문제입니다.

 

후위식 연산이란 연산자가 피연산자 뒤에 있는 표기식입니다.

 

예를 들어 중위표기식이 3+5*2 를 후위표기식으로 표현하면 352*+ 로 표현됩니다.

 

만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면 (3+5)*2 이면 35+2* 로 바꾸어야 합니다.

 

 

노트 메모

(끄적)

내 해답

function mySolution(s){
  const stackNumber = [];
  let result = -1;
  
  for (let i of s) {
    if (isNaN(i)) {
      let a, b, op;
      op = i;
      if (result === -1) {
        a = stackNumber.pop();
        b = stackNumber.pop();
        result = eval(`${a}${op}${b}`)
      } else {
        a = stackNumber.pop();
        result = eval(`${result}${op}${a}`)
      }
    } else {
      stackNumber.push(i)
    }
  }
  
  return result;
}

let str="352+*9-";
console.log(mySolution(str)); // 12 출력

1. 입력한 문자열에 대한 배열을 for 문을 돌면서 숫자인지 아닌지 판단합니다. 
2. 숫자면 Stack 에 push 합니다.
3. 숫자가 아닌 문자(연산자)가 들어오면 Stack 에서 pop 을 한 숫자를 연산자를 통해 계산합니다. 
   이때 맨 처음 계산일 경우 pop 을 2번하여 숫자 2개를 꺼내어 계산하고, 이후에는 result 와 pop 한 숫자 1개를 꺼내서 계산합니다.
4. 해당 결과를 Result 에 저장합니다.
5. Result 를 반환합니다.

 

인프런 해답

function solution(s){  
    let answer;
    let stack=[];
    for(let x of s){
        if(!isNaN(x)) stack.push(Number(x));
        else{
            let rt=stack.pop();
            let lt=stack.pop();
            if(x==='+') stack.push(lt+rt);
            else if(x==='-') stack.push(lt-rt);
            else if(x==='*') stack.push(lt*rt);
            else if(x==='/') stack.push(lt/rt);
        }
    }
    answer=stack[0];
    return answer;
}

let str="352+*9-";
console.log(solution(str));

let str="352+*9-";
console.log(solution(str)); // 12 출력

1. 연산자가 아닌 숫자를 Stack 에 push 합니다.
2. 숫자가 아니라면 Stack 에서 Pop 을 2번 수행합니다.
3. 이때 먼저 pop 한 숫자를 rt 나중에 pop 한 숫자를 lt 로 변수를 할당합니다.
4. 연산자에 맞게 계산하고 결과를 다시 Stack 에 push 합니다.
5. 마지막에 stack[0] 만 남게 되는데 해당 값을 반환합니다.

 

마무리

 

해당 문제를 풀면서 eval 이라는 Javascript 함수를 알수 있었습니다.
(문자열에 연산자가 있으면 계산후에 반환해주는 함수)

 

또 Javascript에서 Stack 사용에 대해 이해할 수 있었습니다.

 

제가 알고리즘쪽 공부를 많이 해보지 않아서 조금 서툴지만 프론트엔드 개발자이긴 해도 알고리즘 공부를 해두면 좋을것 같아서 다시 공부를 시작하고 있습니다.

 

앞으로도 블로그에 꾸준히 알고리즘 관련 포스팅을 써볼 예정입니다.