[백준] 후위 표기식 (1918번)

후위 표기식(Reverse Polish Notation, RPN) 변환 방법

1. 후위 표기식이란?

일반적으로 우리가 사용하는 수식은 중위 표기식(Infix Notation)입니다.
예를 들어:

• 중위 표기식: A + B * C
• 후위 표기식: ABC*+

후위 표기식은 연산자가 피연산자 뒤에 위치하는 표기법으로, 괄호 없이도 연산 순서를 명확히 표현할 수 있습니다.

 

2. 사용되는 자료구조

후위 표기식으로 변환할 때는 스택(Stack)과 큐(Queue) 를 활용합니다.

스택(Stack): 연산자를 저장하는 용도로 사용됩니다.
큐(Queue) 또는 문자열: 변환된 후위 표기식을 저장하는 용도로 사용됩니다.

이유

• 연산자는 우선순위에 따라 LIFO(Last-In-First-Out, 후입선출) 구조인 스택에 저장해야 합니다.
• 피연산자와 우선순위에 따라 정리된 연산자는 FIFO(First-In-First-Out, 선입선출) 구조인 큐 또는 문자열에 저장해야 합니다.

 

3. 핵심 아이디어

1) 피연산자는 큐에 저장하고, 연산자는 스택에 저장하기

• 피연산자는 그대로 출력(또는 큐에 저장)합니다.
• 연산자는 우선순위에 따라 스택에 저장하고 꺼냅니다.

2) 연산자 우선순위 적용하기
연산자의 우선순위는 다음과 같습니다.

• 괄호 (): 최우선
• 곱하기(*), 나누기(/): 우선순위 높음
• 더하기(+), 빼기(-): 우선순위 낮음

3) 피연산자, 괄호, 연산자에 따른 처리 방법

• 피연산자 → 바로 큐에 저장
• 연산자 → 스택에 저장하되, 스택의 top에 있는 연산자보다 우선순위가 낮다면 pop하여 큐에 저장
• 여는 괄호 '(' → 무조건 스택에 저장
• 닫는 괄호 ')' → 여는 괄호 '('가 나올 때까지 스택에서 pop하여 큐에 저장
• 모든 연산을 처리한 후 → 스택에 남아 있는 연산자를 큐로 이동

 

4. 변환 예시

중위 표기식:

 

A + B * C

1. A → 큐에 저장
2. + → 스택에 저장
3. B → 큐에 저장
4. * → +보다 우선순위가 높으므로 스택에 저장
5. C → 큐에 저장
6. 스택에 남은 연산자 *를 큐로 이동
7. 스택에 남은 연산자 +를 큐로 이동

후위 표기식 결과:

ABC*+

 

 

---

정답은 더보기 클릭

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        Stack<Character> stk = new Stack<>();
        String input = br.readLine();
        Queue<Character> queue = new LinkedList<>();

        for (char c : input.toCharArray()) {
            if (Character.isLetter(c)) {
                queue.offer(c);
            } else if (c == '(') {
                stk.push(c);
            } else if (c == ')') {
                while (!stk.isEmpty() && stk.peek() != '(') {
                    queue.offer(stk.pop());
                }
                if (!stk.isEmpty() && stk.peek() == '(') {
                    stk.pop();
                }
            } else {
                while(!stk.isEmpty() && priority(stk.peek()) >= priority(c)) {
                    queue.offer(stk.pop());
                }

                stk.push(c);
            }
        }

        while(!stk.isEmpty()) {
            queue.offer(stk.pop());
        }

        while(!queue.isEmpty()) {
            sb.append(queue.poll());
        }

        System.out.println(sb);
    }

    public static int priority(char c) {
        if (c == '+' || c == '-') {
            return 1;
        } else if (c == '*' || c == '/') {
            return 2;
        }

        return -1;
    }
}

 

5. 정리

• 피연산자는 그대로 출력
• 연산자는 스택을 활용하여 우선순위에 맞게 정리
• 괄호는 특별 처리
• 모든 연산이 끝난 후, 스택에 남은 연산자를 큐로 이동