프로그래머스 | 후위 표기법

📌 문제

중위 표기법(Infix Notation)과 후위 표기법(Postfix Notation)은 수학적인 표현 방법입니다.

중위 표기법은 일반적으로 우리가 일상적으로 사용하는 수식의 표기법입니다. 연산자가 피연산자의 중간에 위치하는 형태를 갖습니다. 예) 2 + 3 * 4
중위 표기법은 연산자 우선순위와 괄호를 고려해야 하기 때문에 해석이 상대적으로 복잡할 수 있습니다.

반면 후위 표기법은 연산자가 피연산자의 뒤에 위치하는 형태를 갖습니다. 예) 2 3 4 * +
후위 표기법은 연산자 우선순위와 괄호의 필요가 없어져서 해석이 간단해집니다.

컴퓨터를 위해 중위 표기법을 후위표기법으로 변환하는 함수를 작성하세요. 단, 연산자와 피연산자 사이에 공백이 한 칸씩 주어지고, 출력 결과에도 모든 연산자와 피연산자 사이에 공백이 한 칸씩 존재해야 합니다.
연산자로 사용되는 기호는 +, -, *, /, (, ) 이며 나머지는 피연산자로 취급합니다.

입출력 예

s	answer
1 + 2 * 3 * ( 2 + 3 )	1 2 3 * 2 3 + * +
2 + 3 * 4	2 3 4 * +

✨ 해결 방법

후위 표기법은 stack을 이용하여 중위 표기법을 후위 표기법으로 변환할 수 있고, 후위 표기법을 계산할 때도 스택을 활용하여 효과적으로 수식을 계산할 수 있습니다.

만약 +와 -가 있다면, 이 연산은 순서대로 실행됩니다.
반면 +와 *가 있다면, 뒤에서부터 실행되겠지요.
(가 나온다면 무조건 괄호 안의 식이 먼저 실행됩니다.

따라서 stack에 연산자를 저장한 후 현재 연산자와 저장된 연산자를 비교하여 현재 연산자의 우선순위가 더 큰 경우는 그대로 더 저장 (이후에 pop 하면 현재 연산자부터 계산하기 때문에) 아닐 경우엔 저장된 연산자를 pop 하여 먼저 계산한 후 현재 연산자를 stack에 저장하면 됩니다.

위 계산방법을 이용하여 중위 표기법을 후위 표기법으로 바꾸는 방법은 다음과 같습니다.

1. 빈 스택을 생성합니다.
2. 피연산자(숫자)일 경우 그대로 출력합니다.
3. 현재 요소가 연산자일 때는 다음과 같은 경우의 수를 갖습니다.
   3-1. 현재 연산자 우선순위 > 스택 마지막 우선 순위 / 현재 연산자가 ( → 현재 요소 push
   3-2. 현재 연산자 우선순위 <= 스택 마지막 우선 순위 → 스택의 마지막 요소 pop하고 출력, 현재 요소 push
   3-3. 현재 연산자가 ) → 스택이 빌 때까지 계속 pop 하고 출력하는데, (를 만난다면 출력하지 않고 버립니다.

---

예시를 들면 아래와 같습니다.
중위 표기법 수식 1 + 2 * 3 * ( 2 + 3 )
후위 표기법 수식 1 2 3 * 2 3 + * +

• 1 출력 : 출력 1
• + 스택에 저장 : 출력 1, 스택 +
• 2 출력 : 출력 1 2, 스택 +
• * 스택에 저장 : 출력 1 2, 스택 + *
• 3 출력 : 출력 1 2 3, 스택 + *
• * 스택에 저장, * 출력 : 1 2 3 *, 스택 + *
• ( 스택에 저장 : 1 2 3 *, 스택 + * (
• 2 출력 : 1 2 3 * 2, 스택 + * (
• + 스택에 저장 : 1 2 3 * 2, 스택 + * ( +
• 3 출력 : 1 2 3 * 2 3, 스택 + * ( +
• ) : 스택 + * ( + 일 때, 뒤에서부터 pop 하면서 출력, 단, (는 그냥 버립니다.

💻 solution

function isOperator(token) {
    return ['+', '-', '*', '/'].includes(token);
}

function getPrecedence(operator) {
    if (operator === '+' || operator === '-') return 1;
    if (operator === '*' || operator === '/') return 2;
    return 0; // 괄호는 가장 낮은 우선순위
}

function solution(S) {
    let stack = [];
    const arr = S.match(/\d+|[+\-*/()]/g) || []; // 숫자 또는 연산자로 매칭
    const answer = [];

    for (let i = 0; i < arr.length; i++) {
        let token = arr[i];

        if (!isNaN(parseInt(token))) {
            answer.push(token);

        } else if (isOperator(token)) {
            while (
                stack.length && getPrecedence(stack[stack.length - 1]) >= getPrecedence(token) && stack[stack.length - 1] !== '(') {
                answer.push(stack.pop());
            }
            stack.push(token);

        } else if (token === '(') {
            stack.push(token);

        } else if (token === ')') {
            while (stack.length && stack[stack.length - 1] !== '(') {
                answer.push(stack.pop());
            }
            stack.pop(); // '(' 제거
        }
    }

    // 스택에 남아있는 모든 연산자를 처리
    while (stack.length) {
        answer.push(stack.pop());
    }
    return answer.join(' ');
}

console.log(solution("12 + 2 * 3 * ( 2 + 3 )"));

1. 연산자 검수 함수

token이 해당하는 연산자 중 하나라면 true를 return합니다.

2. 우선순위를 반환하는 함수

+나 -일 경우 1을, *나 /일 경우 2를, 괄호일 경우 0을 반환합니다.

3. 문자열 S의 공백을 없앤 후 배열로 반환하기

정규 표현식 /\d+|[+\-*/()]/g를 사용합니다.

• \d+ 는 하나 이상의 숫자에 매칭합니다.
• /[\d+\-*/()]/g 로 작성하지 않은 이유는 두 자릿수 이상의 숫자일 경우를 고려해야 하기 때문입니다.
• |는 '또는'을 나타냅니다.
• [+\-*/()] 는 +, -, *, /, (, ) 중 하나에 매칭합니다.
• - 앞에 역 슬래시를 사용한 이유는 -가 문자 클래스([]) 안에서 범위를 나타낼 때 사용되기도 하기 때문입니다.
• g는 전역 검색을 나타냅니다.

4. 변수 선언

stack과 answer를 빈 배열로 생성합니다.

5. 배열을 돌며 본격적인 검사하기

token을 배열의 i 번째 요소라고 가정합니다.
만약 token을 정수로 바꾼 값이 숫자가 아닌 게 아니라면 = 즉 숫자라면, answer에 출력합니다.

그게 아닌 연산자라면,
stack이 비어있지 않고, stack의 마지막 요소의 우선 순위가 token의 우선순위보다 크거나 같고, stack의 마지막 요소가 여는 괄호 (가 아니라면, stack의 마지막 요소를 pop한 후 answer에 넣습니다. 이를 조건 중 하나가 만족하지 않을 때까지 반복합니다.

즉, stack이 다 비워지거나, stack의 마지막 요소의 우선순위가 token보다 작거나, stack의 마지막 요소가 여는 괄호라면 while문이 중단되고 token을 stack에 넣습니다.

만약 token이 일반적인 연산자가 아닌 여는 괄호라면, 그냥 token을 stack에 넣습니다.

이도 아닌 token이 닫는 괄호라면, 다시 while문을 실행합니다.
stack이 비어있지 않고, stack의 마지막 요소가 여는 괄호가 아닐 때까지 stack의 요소를 pop한 후 출력합니다. 만약 여는 괄호를 만났다면 (stack의 요소가 하나 남았다면), 여는 괄호를 stack에서 제거합니다.

6. stack의 남은 요소 처리

만약 반복문을 다 돌았는데도 stack에 연산자가 남아있다면, 뒤에서부터 pop하면서 answer에 넣어줍니다.

7. 공백과 함께 return

이제 answer의 요소들을 공백 ' '으로 join하여 정답을 return 하면 됩니다.