[백준] BOJ_1918 후위 표기식

이종찬·2026년 1월 13일

1. 문제 정보

문제 요약: 사람에게 익숙한 중위 표기식(Infix Notation, 예: A+B)을 컴퓨터가 연산하기 편한 후위 표기식(Postfix Notation, 예: AB+)으로 변환하는 문제입니다. 괄호 처리와 연산자 우선순위를 정확히 반영해야 합니다.
난이도: Gold II
링크: https://www.acmicpc.net/problem/1918

2. 접근 방식

1) 문제의 본질

이 문제는 스택(Stack) 자료구조의 가장 고전적이면서도 강력한 활용 사례입니다. 중위 표기식은 사람의 눈에는 직관적이지만, 컴퓨터가 순차적으로 해석하기에는 '연산 순서의 모호함'이 존재합니다. 예를 들어 A + B * C를 볼 때, +를 먼저 만났음에도 불구하고 뒤에 있는 *를 먼저 수행해야 함을 우리는 '규칙'으로 알고 있습니다.

이 문제의 핵심은 "지금 만난 연산자를 바로 출력할 것인가, 아니면 더 높은 우선순위의 연산자를 위해 잠시 대기(Push)시킬 것인가?"를 결정하는 것입니다. 이를 위해 LIFO(Last-In First-Out) 구조인 스택이 필요합니다.

2) 알고리즘 설계

입력 문자열을 처음부터 끝까지 순회하며 다음과 같은 규칙을 적용합니다.

피연산자(A~Z): 순서가 변하지 않으므로 즉시 출력(StringBuilder에 추가)합니다.
왼쪽 괄호 (: 괄호 안의 연산이 끝날 때까지 대기해야 하므로 무조건 스택에 넣습니다.
오른쪽 괄호 ): 짝이 맞는 (가 나올 때까지 스택에 쌓인 모든 연산자를 꺼내 출력합니다. (괄호 안의 연산 종결)
연산자 (+, -, *, /): 여기가 가장 중요합니다.

스택의 Top에 있는 연산자가 현재 내 연산자보다 우선순위가 높거나 같다면, 그들은 나보다 먼저 연산되어야 합니다. 따라서 스택에서 꺼내 출력합니다.
자신보다 낮은 우선순위가 나올 때까지 반복한 후, 자신을 스택에 넣습니다.

3) 우선순위 정의 및 수식

연산자 간의 우선순위를 수치화하여 함수 $P(op)$ 로 정의하면 로직이 명확해집니다.

P(op) = \begin{cases} 2 & \text{if } op \in \{*, /\} \\ 1 & \text{if } op \in \{+, -\} \\ 0 & \text{otherwise (괄호 등)} \end{cases}

비교 로직: while (stack.notEmpty() && P(current) <= P(stack.peek()))
스택 안의 (는 우선순위가 가장 낮게(0) 취급되어야, ( 위에 다른 연산자가 쌓일 수 있습니다.

3. 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String cmd = br.readLine();

        StringBuilder sb = new StringBuilder();
        // Stack 클래스 대신 ArrayDeque를 사용하여 성능 최적화
        Deque<Character> q = new ArrayDeque<>();

        for (char c : cmd.toCharArray()) {
            if ('A' <= c && c <= 'Z')
                sb.append(c); // 피연산자는 바로 출력
            else if (c == '(')
                q.addLast(c); // 여는 괄호는 무조건 push
            else if (c == ')') {
                // 닫는 괄호가 나오면 여는 괄호가 나올 때까지 pop
                while (!q.isEmpty()) {
                    char ch = q.removeLast();
                    if (ch == '(')
                        break;
                    sb.append(ch);
                }
            } else {
                // 연산자: 스택 top의 우선순위가 나보다 높거나 같으면 pop
                while (!q.isEmpty() && priority(c) <= priority(q.peekLast()))
                    sb.append(q.removeLast());
                q.addLast(c);
            }
        }

        // 스택에 남은 연산자 모두 출력
        while (!q.isEmpty()) {
            sb.append(q.removeLast());
        }

        System.out.println(sb);
    }

    // 연산자 우선순위 부여 함수
    private static int priority(char c) {
        if (c == '*' || c == '/')
            return 2;
        if (c == '+' || c == '-')
            return 1;
        return 0; // '('의 경우 0을 반환하여 스택 안에서 가장 낮은 순위 유지
    }
}