[스택] 후위식 연산

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

후위 연산식이 주어지면 연산한 결과를 출력한다.

만약 3 * ( 5 + 2 ) - 9 를 후위 연산식으로 표현하면 3 5 2 + * 9 - 로 표현되며 그 결과는 12이다. 

 

 

👉 입력

첫 번째 줄에 후위 연산식이 주어진다.

이때 연산식의 길이는 50을 넘지 않으며 1 ~ 9의 숫자와 +, -, *, / 의 네 가지 연산자로만 이루어진다.

 

 

👈 출력

연산한 결과를 출력한다.

 

 

💡 사용된 개념

후위식 연산(postfix)

피연산자가 먼저 쓰이고 그 뒤로 연산자가 나오는 형태이다.

예를 들어 5 + 2를 후위표기식으로 바꾼다면 5 2 +이다.

 

후위 표기식을 계산하는 방법은 다음과 같다.

 

3 5 2 + * 9 -

1. 첫 번째 연산자 + 의 앞에 있는 두 개의 숫자를 더한다. => 3 5 2 + * 9 - => 3 7 * 9 -
2. 두 번째 연산자 * 의 앞에 있는 두 개의 숫자를 곱한다. => 3 7 * 9 - => 21 9 -
3. 세 번째 연산자 - 의 앞에 있는 두 개의 숫자를 뺀다. => 21 9 - => 12

 

 

📝 풀이

 

function solution(s) {
    let answer;
    let stack = [];

    for (const i of s) {
        if (isNaN(i)) {
            let num1 = stack.pop();
            let num2 = stack.pop();

            if (i === "+") stack.push(num2 + num1);
            else if (i === "-") stack.push(num2 - num1);
            else if (i === "*") stack.push(num2 * num1);
            else stack.push(num2 / num1);
        } else stack.push(Number(i));
    }
    answer = stack[0]
    return answer;
}

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

 

스택 역할을 할 배열 stack을 선언한다.

 

for문으로 주어진 후위연산식 s의 각 문자들을 순회한다.

이때 문자가 숫자라면 stack에 숫자형으로 변환한 후 삽입한다.

문자가 숫자가 아니라면(= 연산자라면) stack에서 제일 끝에 저장되어 있던 두 개의 숫자를 꺼낸다.

그리고 해당 문자의 연산에 맞게 연산한 후 다시 stack에 집어넣는다.

 

모든 순회가 끝났다면 stack에는 식이 계산된 결과만이 남게 된다.

따라서 이것을 answer에 담고 반환, 출력한다.

 

어차피 식이 계산된 결과만이 남게 되니 answer = stack.pop()을 해도 괜찮을 것 같다.